Link to the Problem
Thought Process
Although we don’t directly know the number of ways in which we can reach step n, we know the number of ways for reaching steps 1 and 2. Step 1 can only be reach in 1 way and i.e. by taking 1 step from step no. 0. Step 2 can be reached in 2 ways i.e. from 0 to 1 and 1 to 2, or from 0 to 2. So we already know the answers when n=1 and n=2. Now, for 3rd step, we can not directly go from 0 to step 3. But we know that from step 1 and step 2, we can directly reach the step 3 by taking 2 steps or 1 step at a time respectively. Now that we know 3rd step can be reached directly from 1st and 2nd, what will be the number of ways in which we can reach the step 3? It would be all the ways in which we can reach the step 1 (because we can always take 2 steps from here to reach the step 3) + the number of ways in which we can reach the step 2 (because we can always take 1 more step to reach the step 3). We can apply the same thinking for step 4, 5, and up to n. Generalizing this for any step n is trivial: f(n) = f(n-1) + f(n-2).
Algorithm
- Store the answers for known values of steps.
- Build from bottom to top.
- For each value of n,
f(n) = f(n-1) + f(n-2). - Return the answer.
Code
| class Solution { | |
| public: | |
| int climbStairs(int n) { | |
| vector<int> dp(n+1) = {0, 1, 2}; // Stores number of ways in which | |
| // i-th step can be reached, at | |
| // location dp[i]. | |
| for (int i=3; i<=n; i++) { // For each step - (bottom to top) | |
| dp[i] = dp[i-1] + dp[i-2]; // All the ways in which (i-1)-th | |
| // step can be reached AND all the | |
| // ways in which (i-2)-th step can | |
| // be reached | |
| } | |
| return dp[n]; // Return answer. | |
| } | |
| }; |
The approach we discussed here is bottom-up approach which uses the technique of tabulation. This can also be solved in top-down approach with memoization.
Is there anything that is still unclear? Let me know in the comments and I can elaborate further.
Don’t forget like & share the post, and subscribe to the blog to get notifications whenever solution to a new problem is added.
Happy Coding!
Similar Problems
Leetcode 509. Fibonacci Number
