LeetCode 70 爬楼梯

动态规划

const int N = 50;
class Solution {
public:
    int dp[N];
    int climbStairs(int n) {
        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 dp[2];
    int climbStairs(int n) {
        dp[0] = 1;
        dp[1] = 1;

        for (int i = 2; i <= n; i ++) {
            int temp = dp[1];
            dp[1] = dp[0] + dp[1];
            dp[0] = temp;
        }

        return dp[1];
    }
};