代码随想录算法训练营 ---第四十八天

第一题：

简介：

注：本题简介是我的思路，题解思路看下方。

动态规划五部曲：

1.确定dp数组的含义

//dp[i]表示偷到第i家能偷到的最大金额

 for(int i=2;i<nums.size();i++){
            if(i-3>=0)
            dp[i] = max(dp[i-2],dp[i-3])+nums[i];
            else{
                 dp[i] = dp[i-2]+nums[i];
            }
        }

2.确定递归公式

            if(i-3>=0){
                 dp[i] = max(dp[i-2],dp[i-3])+nums[i];
             }
            else{
                 dp[i] = dp[i-2]+nums[i];
            }

3.确定初始化

dp[0] = nums[0];

dp[1] = nums[1];

4.确定遍历顺序

5.打印数组

题解思路：

确定dp数组（dp table）以及下标的含义

dp[i]：考虑下标i（包括i）以内的房屋，最多可以偷窃的金额为dp[i]。

2 .确定递推公式

决定dp[i]的因素就是第i房间偷还是不偷。如果偷第i房间，那么dp[i] = dp[i - 2] + nums[i] ，即：第i-1房一定是不考虑的，找出下标i-2（包括i-2）以内的房屋，最多可以偷窃的金额为dp[i-2] 加上第i房间偷到的钱。如果不偷第i房间，那么dp[i] = dp[i - 1]，即考虑i-1房（注意这里是考虑，并不是一定要偷i-1房）然后dp[i]取最大值，即dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);

3.dp数组如何初始化

dp[0] 一定是 nums[0]

dp[1]就是nums[0]和nums[1]的最大值即：dp[1] = max(nums[0], nums[1]);

代码如下：

vector<int> dp(nums.size());
dp[0] = nums[0];
dp[1] = max(nums[0], nums[1]);

4.确定遍历顺序

dp[i] 是根据dp[i - 2] 和 dp[i - 1] 推导出来的，那么一定是从前到后遍历！

代码如下：

for (int i = 2; i < nums.size(); i++) {
    dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);
}

5.举例推导dp数组

以示例二，输入[2,7,9,3,1]为例。

198.打家劫舍

代码实现：

class Solution {
public:
    //dp[i]表示 偷到第i家能偷到的最大金额
    int rob(vector<int>& nums) {
        if(nums.size() == 1)return nums[0];
        vector<int> dp(nums.size(),0);
        dp[0] = nums[0];
        dp[1] = nums[1];
        for(int i=2;i<nums.size();i++){
            if(i-3>=0)
            dp[i] = max(dp[i-2],dp[i-3])+nums[i];
            else{
                 dp[i] = dp[i-2]+nums[i];
            }
        }
        return dp.back()>dp[dp.size()-2]?dp.back():dp[dp.size()-2];
    }
};

题解代码实现：

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

第二题：

简介：

对于一个数组，成环的话主要有如下三种情况：

情况一：考虑不包含首尾元素

213.打家劫舍II

情况二：考虑包含首元素，不包含尾元素

213.打家劫舍II1

情况三：考虑包含尾元素，不包含首元素

213.打家劫舍II2

但是我们可以看出情况二三都包含了情况一的情况。所以我们算出情况二和情况三分别可以获得的最大利益。再进行比较就可以了。

代码实现：

class Solution {
public:
    //偷盗第i家的最大值
    int rob(vector<int>& nums) {
      if (nums.size() == 0) return 0;
        if (nums.size() == 1) return nums[0];
        int result1 = robRange(nums, 0, nums.size() - 2); // 情况二
        int result2 = robRange(nums, 1, nums.size() - 1); // 情况三
        return max(result1, result2);
    }
     int robRange(vector<int>& nums, int start, int end) {
        if (end == start) return nums[start];
        vector<int> dp(nums.size());
        dp[start] = nums[start];
        dp[start + 1] = max(nums[start], nums[start + 1]);
        for (int i = start + 2; i <= end; i++) {
            dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);
        }
        return dp[end];
    }
};

第三题：

简介：

代码随想录：打家劫舍3本题建议看卡哥的视频讲解和题解

代码实现：

class Solution {
public:
     //dp[0] 表示不偷  dp[1]表示偷
    vector<int> robtree(TreeNode* cur){
        if (cur == NULL) return vector<int>{0, 0};
        vector<int> left = robtree(cur->left);
        vector<int> right = robtree(cur->right);
        // 偷cur，那么就不能偷左右节点。
        int val1 = cur->val + left[0] + right[0];
        // 不偷cur，那么可以偷也可以不偷左右节点，则取较大的情况
        int val2 = max(left[0], left[1]) + max(right[0], right[1]);
        return {val2, val1};
    }
    int rob(TreeNode* root) {
        vector<int> result = robtree(root);
        return max(result[0], result[1]);
          
    }
};