Question Link and Solution

You are climbing a staircase. It takes n steps to reach the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Solution :

Intuition to this question:

• if 1 stair ==> 1 step possible

• if 2 stairs ==> 2 steps ==> 1->2 or directly to the otp

• if 3 stairs ==> 3 steps ==> 1->2->3 or 1->3 or 2->3(directly jumping to 2)

• if 4 stairs ==> 5 steps => 1->2->3->4 | 1->2->4 | 1->2->4 | 2->3->4 | 2->4 ==> total of 5 steps.

• if 5 stairs ==> 1->2->3->4->5 | 1->2->3->5 | 1->2->4->5 | 1->3->4->5 1->3->5 | 2->3->4->5 | 2->3->5 ==> total of 7 steps

so by observation, we can see that, from 3 number of stairs, we're repeating/overlapping our old answers ==> Dynamic Programming.

Approach :

1. declare dp[] array of size (n+1)

2. initialize dp[1] = 1, dp[2] = 1

3. Now we can say dp[3] would be dp[2] + dp[1]

4. so make a while/for loop which runs till i<=n(as we're using dp[n+1]), use this formula inside it: dp[i] = dp[i-1]+dp[i-2]

5. At last return dp[n]

6. In the beginning, if size of stairs is 1 or 2 or 0 then return 1 or 2 or 0 respectively.

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