2021-10-31 leetcode 动态规划 198.打家劫舍 213.打家劫舍2 c++

2021-10-31 leetcode 动态规划 198.打家劫舍 213.打家劫舍2 c++

1leetcode 98.打家劫舍

要素
不能连续盗窃，求盗窃最大金额
思路
用dp[i][2]来表示盗窃最大金额
dp[i][0]: 对第i家未进行盗窃的状态下累积之前的最大盗窃金额
dp[i][1]: 对第i家进行盗窃的状态下(对第i家盗窃则意味着对第i-1家未进行盗窃)累积之前的最大盗窃金额

可得状态转移方程如下
（1）dp[i][0] = max(dp[i-1][0], dp[i-1][1])
（2）dp[i][1] = dp[i-1][0] + nums[i]

AC代码

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

leetcode 213.打家劫舍2
三种情况：
（1）1家，则只打劫这一家
（2）2家，选金额大的打劫
（3）>=3家

	（1）不看第1家，从第二家开始算得最佳的情况放入dp数组
	（2）不看最后一家，从第一家开始算得最佳情况放入dp数组当中
	（3）将情况1和情况2比较大小，取最大值就可以得到结果。
	 即 不看首/尾，重复两次198.打家劫舍的思路。

AC代码

class Solution {
public:
    int rob(vector& nums) {
        int l = nums.size();
        //1
        if(l == 1)
            return nums[0];
        //2
        if(l == 2)
            return nums[0] > nums[1] ? nums[0] : nums[1];
        //>=3
        int dp[l][2];
        //（1）
        dp[0][0] = 0;
        dp[0][1] = nums[0];
        for(int i = 1; i < l-1; i++) {
            dp[i][0] = max(dp[i-1][0], dp[i-1][1]);//unrob
            dp[i][1] = dp[i-1][0] + nums[i];//rob
        }
        int a = max(dp[l-2][0], dp[l-2][1]);
        //（2）
        dp[1][0] = 0;
        dp[1][1] = nums[1];
        for(int i = 2; i < l; i++) {
            dp[i][0] = max(dp[i-1][0], dp[i-1][1]);//unrob
            dp[i][1] = dp[i-1][0] + nums[i];//rob
        }
        int b = max(dp[l-1][0], dp[l-1][1]);
        //（3）
        return a > b ? a : b;
    }
};