剑指 Offer II 动态规划

088. 爬楼梯的最少成本

class Solution {
public:
    int minCostClimbingStairs(vector& cost) {
        int n=cost.size();
        vectorf(n+1);
        f[0]=cost[0],f[1]=cost[1];

        //走到第i级台阶 最小代价
        //状态转移 从前一个或 前两个走上来
        cost.push_back(0);
        for(int i=2;i<=n;i++)
        {
            f[i]=cost[i]+min(f[i-1],f[i-2]);
        }
        return f[n];
    }
};

089. 房屋偷盗

class Solution {
public:
    int rob(vector& nums) {
        int n=nums.size();
        vector>f(n,vector(2));
        f[0][0]=0;
        f[0][1]=nums[0];
        for(int i=1;i=2){
               // f[i][0]=max(f[i][0],f[i-2][1]);
                f[i][1]=max(f[i][1],f[i-2][1]+nums[i]);
            }
            
        }
        return max(f[n-1][0],f[n-1][1]);
    }
};

091. 粉刷房子

class Solution {
public:
/*
f[i][j]

j是颜色 从另外两个转移
*/
    int minCost(vector>& cost) {
        int n=cost.size();
        vector>f(n,vector(3));
        f[0][0]=cost[0][0],f[0][1]=cost[0][1],f[0][2]=cost[0][2];

        for(int i=1;i