April 09, 2019

70. Climbing Stairs

法1. DP

入门 DP 题。动态规划用于记数。

因为每次可以走 1 step 或者 2 steps，所以走 n steps 的 distinct ways = 走 (n - 1) step 的 distinct ways + 走 (n - 2) step 的 distinct ways。

Time = O(n), Space = O(n)

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

优化 Space -> O(1):

class Solution {
    public int climbStairs(int n) {
        int stair0 = 1;
        int stair1 = 1;
        int cur = 1;
        for (int i = 2; i < n + 1; i++) {
            cur = stair0 + stair1;
            stair1 = stair0;
            stair0 = cur;
        }
        return cur;
    }
}

法2. Recursion (With Memorization)

class Solution {
    public int climbStairs(int n) {
        int[] visited = new int[n + 1];
        return climbStairs(n, visited);
    }
    
    private int climbStairs(int n, int[] visited) {
        if (visited[n] > 0) {
            return visited[n];
        }
        if (n == 0 || n == 1) {
            return 1; // pay attention here. 
        } 
        int res = climbStairs(n - 1, visited) + climbStairs(n - 2, visited);
        visited[n] = res;
        return res;
    }
}