当前位置：首页 > article >正文

代码随想录打卡Day39

article 2024/9/27 7:44:45

今天是打家劫舍专题，三道题全都看了讲解，第一次做感觉确实是无从下手。。。不过了解了原理之后代码很快就写出来了。

198.打家劫舍

这道题使用一维dp数组，首先确定dp数组的含义，dp[i]为考虑偷下标[0, i]家的情况下所能获得的最大收益，对于每一家，都有两个状态，偷与不偷，当选择偷时，则收益为当前房子的金币 + 上上个房子的最大收益（上上个房子不一定非要偷），当选择不偷时，其收益为上个房子的最大收益（可偷可不偷）。

class Solution {
public:
    int rob(vector<int>& nums) {
        //1.确定dp[i]的含义：考虑下标在[0, i]的房间的情况下，所能偷的最多的钱为dp[i]
        //2.确定递推公式  dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);
        //3.dp数组初始化 dp[0] = nums[0], dp[1] = max(nums[0], nums[1]);
        //4.确定遍历顺序：从小到大遍历
        //5.打印数组(省略)
        vector<int> dp(nums.size());
        //初始化
        dp[0] = nums[0];
        if(nums.size() > 1)
            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.back();
    }
};

213.打家劫舍II

这个环形问题我一开始想的是用求余操作来解决，但是想了半天也没想出来用求余怎么做，于是还是去看视频了。。这个环形问题主要还是拆解成两个线性问题，首元素和尾元素不能同时纳入考虑范围，所以构造两个数组，一个是不包含尾元素的向量，另一个是不包含首元素的向量，这就转换成了上一道题的思路，分别对两个线性表求最大收益，取其中的较大值返回即可。

class Solution {
public:
    int rob(vector<int>& nums) {
        //1.确定dp[i]的含义：考虑下标在[0, i]的房间的情况下，所能偷的最多的钱为dp[i]
        //2.确定递推公式  dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);
        //3.dp数组初始化 dp[0] = nums[0], dp[1] = max(nums[0], nums[1]);
        //4.确定遍历顺序：从小到大遍历
        //5.打印数组(省略)
        if(nums.size() == 1) return nums[0];
        //考虑首元素而不考虑尾元素的情况
        vector<int> nums1(nums.begin(), nums.end() - 1); //[0, nums.size() - 2]
        //考虑尾元素而不考虑首元素的情况
        vector<int> nums2(nums.begin() + 1, nums.end()); //[1, nums.size() - 1]
        vector<int> dp1(nums1.size());
        vector<int> dp2(nums2.size());
        dp1[0] = nums1[0];
        dp2[0] = nums2[0];
        if(dp1.size() > 1){
            dp1[1] = max(nums1[0], nums1[1]);
            dp2[1] = max(nums2[0], nums2[1]);
        }
        for(int i = 2; i < nums1.size(); i++){
            dp1[i] = max(dp1[i - 2] + nums1[i], dp1[i - 1]);
            dp2[i] = max(dp2[i - 2] + nums2[i], dp2[i - 1]);
        }  
        return max(dp1.back(), dp2.back());
    }
};

337.打家劫舍III

这道题是树形dp，以前从来没见过，感觉对我来说确实还是太难了。这道题需要用一个大小为2的一维数组保存每一个节点偷与不偷时的最大收益，通过递归遍历二叉树的所有节点，得到每个节点偷与不偷时的最大收益，这里直接定义一个返回向量的递归遍历函数，当选择偷根节点时，左右孩子都不能偷，则收益为root -> val + left_dp[1] + right_dp[1]，选择不偷根节点时，则返回左右孩子各自的最大收益的总和（并不是根节点没偷就一定要偷其左右孩子），则收益为max(left_dp[0], left_dp[1]) + max(right_dp[0], right_dp[1])。在主函数中直接拿一个向量接住调用遍历函数且输入参数为根节点root时的结果，再返回向量中的较大值即可。

class Solution {
public:
    vector<int> Travelsal(TreeNode* root){
        //确定终止条件
        if(root == NULL) return {0, 0};
        //后序遍历,dp[0]为偷时的最大金币，dp[1]为不偷时的最大金币
        vector<int> left_dp = Travelsal(root -> left);  //左孩子节点偷与不偷
        vector<int> right_dp = Travelsal(root -> right); //右孩子节点偷与不偷
        vector<int> root_dp;
        //根节点选择偷,左孩子和右孩子都不能偷
        root_dp.push_back(left_dp[1] + right_dp[1] + root -> val);
        //根节点选择不偷，则左孩子和右孩子可偷可不偷，取决于哪种状态的收益更大
        root_dp.push_back(max(left_dp[0], left_dp[1]) + max(right_dp[0], right_dp[1]));
        return root_dp;
    }
    int rob(TreeNode* root) {
        vector<int> dp = Travelsal(root);
        return max(dp[0], dp[1]);
    }
};