Blog

Introduction

• In this article we will solve Leetcode #70. This problem is best problem to start learning about dynamic programming. It’s classic!

Problem Statement

• We have to climb staircase. we can take up-to n steps to reach top.
• Each time we can either take 1 step or 2 step. We need to find out in how many ways we can climb to the top.

Solutions

• We can solve this problem using dynamic programming. In dynamic programming our major goal is to break down large problem into subproblems.
• So we have to climb N steps , then how about N-1 , how about N-2 ,… how about 2 steps, how about 1 steps and how about 0 steps.
• So we bring down to the base of the problem and find answers upwards.
• There are 2 ways to solve DP problem , either top down or bottom up. We will solve in both ways.

Solution #1 : (Top Down)

• Let’s solve using top down approach. Top down approach is nothing but backtracking/ recursion with some cache/memoization. 
• Cache/Memoization help us to avoid recompute already computed subproblems.
• We first need to figure out what would be the base case. In this problem, if steps that we are taking is more than n , then we can return 0 because then we don’t have any ways to reach top, we are already ahead of top.
• If our current steps at top then we can say that we found 1 way to reach to the top.
• If our current step is already computed by some other subproblem then we already have that in our cache then just return it instead of making recursion call again.
• Once we are done with base cases then we can focus on main logic. At each step we can either take 1 step or 2 step , so we will make backtrack call at index+1 and index+2 step and sum them because these call will return number of ways to reach the top when we take 1 step and when we take 2 step.
• The we save this result to our cache , in case if we reach to index again to avoid recomputing.

private int backtrack(int index, int n){
        if(index > n) return 0;
        if(cache[index] != null) return cache[index];
        
        if(index==n){
            return 1;
        }
        
        int res = backtrack(index+1, n) + backtrack(index+2, n);
        cache[index] = res;
        return res;
}

Solution #2 : (Bottom Up)

• We will solve using bottom up approach. In this case we initialize cache/dp array with base cases.
• So in case when we have 0 steps then we can reach to top in 0 ways.
  when we have 1 steps then we can reach to the top in 1 way.
  when we have 2 steps then we can reach to the top in 2 ways.
• Now we can use these base cases to form other steps by iterating over loop until n steps.
• Basically in order to reach @ step 3 , we can either come from step 2 or step 1. So we add both of them. it takes 1 way to reach step and it takes 2 ways to reach step. hence to reach 3 -> 1+2 = 3 ways.
• Similarly @ step 4 = step 3+step 2 = 3+2 = 5 ways and so on.
• The cache[N] will store our final result to reach at n step. we can just return it.

class Solution {

    public int climbStairs(int n) {
        cache = new Integer[n+1];
        
        if(n<3){
          if(n==0) return 0;
          if(n==1) return 1;
          if(n==2) return 2;
        }
            cache[0] = 0;
            cache[1] = 1;
            cache[2] = 2;
            for(int i=3;i<=n;i++){
                cache[i] = cache[i-1]+cache[i-2];
            }
        
        return cache[n];
    }
 }

Submission

• Our solution is accepted by Leetcode and we passed all the test cases.

Conclusion

• In this article we solved leetcode 70 problem. This problem is good practice to learn about dynamic programming both top down and bottom approach.

Bonus Tip

• If you want to upskill your coding interview game, you can definitely check out this bestseller course ( this is in Java )