Leetcode 70. Climbing Stairs

Link to the Problem

Climbing Stairs

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

  1. Store the answers for known values of steps.
  2. Build from bottom to top.
  3. For each value of n, f(n) = f(n-1) + f(n-2).
  4. 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.
}
};
view raw Leetcode_70.cpp hosted with ❤ by GitHub

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



Related Posts


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s