70. Climbing Stairs.md

70. Climbing Stairs

思路

简单的动态规划。
按照最后是跨一步还是两步可以将到达第n步的所有情况分为两种：

• 1、从第n-2步阶梯一下跨两步到第n步阶梯；
• 2、从第n-1步阶梯跨一步到第n步阶梯；
  即若dp[i]代表跨到第i步阶梯的情况数，那么dp[i] = dp[i - 1] + dp[i - 2]，所以这其实就是斐波那契数列，见509. Fibonacci Number。

时间复杂度和空间复杂度都为O(n)，可将空间复杂度优化为O(1)

还有一个复杂度为O(logN)求斐波那契数列的思路，详见509题解。

C++

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

空间优化后的版本:

class Solution {
public:
    int climbStairs(int n) {
        int tmp, pre = 1, res = 1;
        for(int i = 2; i <= n;i++){
            tmp = res;
            res += pre;
            pre = tmp;
        }
        return res;
    }
};