70. Climbing Stairs

Link

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Note: Given n will be a positive integer.

Example 1:

Input: 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps

Example 2:

Input: 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

Solution

Recursion

public int climbStairs(int n) {

    if(n == 0) return 0;
    if(n == 1) return 1;
    if(n == 2) return 2;
    return climbStairs(n-1) + climbStairs(n-2);
}

solve with memorization

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

flip that around (Top down)反過來想 (dynamic approach)

由base case開始到往下， 到下個位置的方法數，一直累加直到n。

     public int climbStairs(int n) {
        if ( n == 0) return 1;
        if ( n == 1 ) return 1;
        if ( n == 2 ) return 2;
        int all_ways = 0;
        int way_from_two_Step_Before = 1;
        int way_from_one_Step_Before = 2;
        for( int i = 3; i <= n ; i++){
            all_ways = way_from_one_Step_Before + way_from_two_Step_Before ;
            //update the ways of oneStep/twoStep for next distance
            way_from_two_Step_Before = way_from_one_Step_Before ;
            way_from_one_Step_Before = all_ways;
        }
        return all_ways;
    }