LeetCode 70 Climbing Stairs

LeetCode 70

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?

Diffculty Easy

Similar Problems [LeetCode 91] Decode Ways Medium [LeetCode 96] Unique Binary Search Trees Medium

Analysis

入门的 DP 题目，DP 实质就是 cache, 把之前出现过的中间结果记录，下次再出现相同情况的时候，通过 DP table 可以只用 O(1) 的时间复杂度得到。 dp[i] 表示到达第 i 层楼梯的不同走法。 那么题目中每次可以选择走一步，或者两步，dp[i] = dp[i-1] - dp[i-2]。 从迭代公式可以知道，初始情况有两种：dp[0] 和 dp[1]。

优化 可以只用三个变量，减少空间使用。

Solutions

1. DP

class Solution {
public:
    int climbStairs(int n) {
        vector<int> dp(n + 1, 0);
        dp[1] = 1, dp[2] = 2;
        for (int i = 3; i <= n; ++i) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
};

1. Three Variables

(1) Array of size 3

int climbStairs2(int n) {
    vector<int> res(3);  
    res[0] = 1;  
    res[1] = 1;  
    for (int i = 2; i <= n; i++) {
        res[i%3] = res[(i-1)%3] + res[(i-2)%3];  
    }  
    return res[n%3];  
}

(2) 3 variables

int climbStairs(int n) {
    if (n < 4) return n;  
    int a = 2, b = 3, c = 5;  
    for (int i = 5; i <= n; i++) {
        a = c;  
        c = b+c;  
        b = a;  
    }  
    return c;  
}

Reference