Problem Statement

Given a stair with 'n' steps, implement a method to count how many possible ways are there to reach the top of the staircase, given that, at every step you can either take 1 step, 2 steps, or 3 steps.

Example 1:

Number of stairs (n) : 3
Number of ways = 4
Explanation: Following are the four ways we can climb : {1,1,1}, {1,2}, {2,1}, {3} 

Example 2:

Number of stairs (n) : 4
Number of ways = 7
Explanation: Following are the seven ways we can climb : {1,1,1,1}, {1,1,2}, {1,2,1}, {2,1,1}, 
{2,2}, {1,3}, {3,1}

Constraints:

• 1 <= n <= 45

Let's first start with a recursive brute-force solution.

Why this is a Fibonacci Numbers problem

This is the count the ways to arrive variant: one state is the number of routes that reach position i.

The closest alternative. Generate every sequence of steps and count them, which is the Subsets pattern. With n at 45 the count of routes is in the trillions, so listing them is impossible while counting them is instant.

That gap is the lesson. The last move onto step n was a 1, a 2 or a 3, and those three cases cover every route without overlapping. So the ways to reach n are the ways to reach n minus 1, n minus 2 and n minus 3, added. It is Fibonacci with three terms instead of two, which is why the chapter puts it second.

Basic Solution

At every step, we have three options: either jump 1 step, 2 steps, or 3 steps. So our algorithm will look like this:

The time complexity of the above algorithm is exponential O(3^n) as we are making three recursive call in the same function. The space complexity is O(n) which is used to store the recursion stack.

Let's visually draw the recursion for CountWays(4) to see the overlapping subproblems:

We can clearly see the overlapping subproblem pattern: CountWays(2) and CountWays(1) have been called twice. We can optimize this using memoization.

Top-down Dynamic Programming with Memoization

We can use an array to store the already solved subproblems. Here is the code:

What is the time and space complexity of the above solution? Since our memoization array dp[n+1] stores the results for all the subproblems, we can conclude that we will not have more than n+1 subproblems (where 'n' represents the total number of steps). This means that our time complexity will be O(N). The space complexity will also be O(n); this space will be used to store the recursion-stack.

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 previous three counts. We can use this fact to populate our array.

Code

Here is the code for our bottom-up dynamic programming approach: