代码随想录打卡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]);}
};