0% completed
Problem Statement
Given a number 'n', implement a method to count how many possible ways there are to express 'n' as the sum of 1, 3, or 4.
Example 1:
n : 4
Number of ways = 4
Explanation: Following are the four ways we can express 'n' : {1,1,1,1}, {1,3}, {3,1}, {4}
Example 2:
n : 5
Number of ways = 6
Explanation: Following are the six ways we can express 'n' : {1,1,1,1,1}, {1,1,3}, {1,3,1}, {3,1,1},
{1,4}, {4,1}
Let's first start with a recursive brute-force solution.
Basic Solution
For every number 'i', we have three option: subtract either 1, 3, or 4 from 'i' and recursively process the remaining number. So our algorithm will look like:
The time complexity of the above algorithm is exponential O(3^n). The space complexity is O(n) which is used to store the recursion stack.
Let's visually draw the recursion for CountWays(5)
to see the overlapping subproblems:

We can clearly see the overlapping subproblem pattern: CountWays(3)
, CountWays(2)
and CountWays(1)
have been called twice. We can optimize this using memoization to store the results for subproblems.
Top-down Dynamic Programming with Memoization
We can use an array to store the already solved subproblems. Here is the code:
Bottom-up Dynamic Programming
Let's try to populate our dp[]
array from the above solution, working in a bottom-up fashion. As we saw in the above code, every CountWaysRecursive(n)
is the sum of the three counts. We can use this fact to populate our array.
Code
Here is the code for our bottom-up dynamic programming approach:
The above solution has a time and space complexity of O(n) and O(1) respectively.
Fibonacci number pattern
We can clearly see that this problem follows the Fibonacci number pattern. However, every number in a Fibonacci series is the sum of the previous two numbers, whereas in this problem every count is a sum of previous three numbers: previous-1, previous-3, and previous-4. Here is the recursive formula for this problem:
CountWays(n) = CountWays(n-1) + CountWays(n-3) + CountWays(n-4), for n >= 4
.....
.....
.....
Table of Contents
Contents are not accessible
Contents are not accessible
Contents are not accessible
Contents are not accessible
Contents are not accessible