代码随想录打卡Day39
今天是打家劫舍专题，三道题全都看了讲解，第一次做感觉确实是无从下手。。。不过了解了原理之后代码很快就写出来了。
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]);
}
};
明天就可以休息了，nice！！
原文地址：https://blog.csdn.net/weixin_52151595/article/details/142418891
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！