2020-05-31 70. Climbing Stairs E

https://leetcode.com/problems/climbing-stairs/

My answer / AC

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function(n) {
    let dp = []
    dp[0] = 1;
    dp[1] = 1;
    for(let i=2; i<=n; i++){
        dp[i] = dp[i-1]+dp[i-2];
    }
    return dp[n];
};

Complexity Analysis

Time complexity : O(n)O(n). Single loop upto nn.

Space complexity : O(n)O(n). dpdp array of size nn is used.

Best answer

public class Solution {
    public int climbStairs(int n) {
        int memo[] = new int[n + 1];
        return climb_Stairs(0, n, memo);
    }
    public int climb_Stairs(int i, int n, int memo[]) {
        if (i > n) {
            return 0;
        }
        if (i == n) {
            return 1;
        }
        if (memo[i] > 0) {
            return memo[i];
        }
        memo[i] = climb_Stairs(i + 1, n, memo) + climb_Stairs(i + 2, n, memo);
        return memo[i];
    }
}

Approach 2: Recursion with Memoization
Algorithm

In the previous approach（Brutal Force） we are redundantly calculating the result for every step. Instead, we can store the result at each step in memomemo array and directly returning the result from the memo array whenever that function is called again.

In this way we are pruning recursion tree with the help of memomemo array and reducing the size of recursion tree upto nn.

Complexity Analysis

Time complexity : O(n)O(n). Size of recursion tree can go upto nn.

Space complexity : O(n)O(n). The depth of recursion tree can go upto nn.

Recap

• 今天是动规集训，刷刷刷
• 找好状态转移的点，由前面决定后面的变化