LeetCode-dp

leetcode 101的动态规划专题

基本动态规划：一维

70. 爬楼梯

class Solution {
public:
    int climbStairs(int n) {
        int a=1,b=2;
        if(n<2) return 1; 
        for(int i = 2; i <n ; i++) {
            int c = a+b;
            a=b;
            b=c;
        }
        return b;
    }
};

dp数组表示上n层楼有几种可能
转移方程是 $ dp[i] = dp[i-1] + dp[i-2] $
上到第i层有可能从第i-1层或i-2层上来，则上到i层的可能数目就是 $ dp[i-1] + dp[i-2] $
由于dp[i]只需要前两个数的数据，所以可以优化掉dp数组，用两个变量代替，节省数组空间

198. 打家劫舍