Day48_动态规划

29. 打家劫舍

198. 打家劫舍
思路：

题目的关键是，不能偷相邻的两个屋子，即只能偷上一个屋子不偷当前屋子，或者不偷上一个屋子偷当前屋子。

1. dp[i] 表示偷到第 i 个屋子最大的偷盗额
2. dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]) 表示选择偷与不偷的最大收益值
3. 初始化，没有屋子偷盗最大为0，有1间屋子偷之，两间屋子偷第一间与第二间中的最大者
4. 由于每次递推都是从前 一|两 间屋子的最大收益递推得来，所以遍历顺序从前往后

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

30. 打家劫舍 II

213. 打家劫舍 II
思路：

与上一问的不同之处在于出现了环，分三种情况考虑

1. 偷第一间不偷最后一间
2. 偷最后一间不偷第一间
3. 第一间和最后一间都不偷
   由于前两种情况在计算时把第三种情况的运算包含在内了，所以忽略之

class Solution {
public:// 稍作修改，复用第一问代码int rob_dp(vector<int>& nums, int start, int end) {int nums_size = end - start + 1;if (nums_size == 0) return 0;if (nums_size == 1) return nums[start];vector<int> dp(nums_size, 0);dp[0] = nums[start];dp[1] = max(nums[start], nums[start + 1]);for (int i = 2; i < nums_size; i++) {dp[i] = max(dp[i - 1], dp[i - 2] + nums[start + i]);}return dp[nums_size - 1];}int rob(vector<int>& nums) {int nums_size = nums.size();if (nums_size == 0) return 0;if (nums_size == 1) return nums[0];return max(rob_dp(nums, 0, nums_size - 2), rob_dp(nums, 1, nums_size - 1)); }
};

31. 打家劫舍 III

337. 打家劫舍 III
思路1：

后续遍历，爆搜,TLE

时间复杂度：$O(n^2)$ 由于算了每两个子节点，同时会对其四个子树遍历一次，每一层都如此，复杂度粗糙估计为 $n^2$
空间复杂度：$O(logn)$ 算上递推系统栈的空间

class Solution {
public:int rob(TreeNode* root) {if (root == nullptr) return 0;if (root->left == nullptr && root->right == nullptr) return root->val;// 偷当前结点int var_cur_1 = root->val;if (root->left) var_cur_1 += rob(root->left->left) + rob(root->left->right);if (root->right) var_cur_1 += rob(root->right->left) + rob(root->right->right);// 不偷当前结点、int var_cur_0 = 0;var_cur_0 += rob(root->left) + rob(root->right);return max(var_cur_0, var_cur_1);}
};

思路二：

爆搜超时是因为有些搜过的点已经得到了最大收益值，却被多次重复搜索导致的，利用记忆化搜索优化一下就能过了

时间复杂度：$O(n)$
空间复杂度：$O(logn)$ 算上递推系统栈的空间

class Solution {
public:unordered_map<TreeNode*, int> umap;int rob(TreeNode* root) {if (root == nullptr) return 0;if (root->left == nullptr && root->right == nullptr) return root->val;if (umap[root]) return umap[root];// 偷当前结点int var_cur_1 = root->val;if (root->left) var_cur_1 += rob(root->left->left) + rob(root->left->right);if (root->right) var_cur_1 += rob(root->right->left) + rob(root->right->right);// 不偷当前结点、int var_cur_0 = 0;var_cur_0 += rob(root->left) + rob(root->right);umap[root] = max(var_cur_0, var_cur_1);return umap[root];}
};

思路三：
树形dp入门

对树的每个结点维护一个包含两个数的dp(var_cur_0, var_cur_1)值
var_cur_0：不偷当前结点的最大收益
var_cur_1：偷当前结点的最大收益
dp的过程是后续遍历，每次根节点的递推过程要用到子树的递推结果
那么偷的过程还是不能同时偷一对父子结点，那么偷的方法就有如下两种：

1. 偷当前结点，那么就不能偷其左右子节点，递推利用的就是左右子节点的 var_cur_0 相加，再加上当前结点的值
2. 不偷当前结点，那么子节点无所谓偷不偷，只要最大化收益即可，于是递推利用左右子树偷盗的最大值相加
   示意图如下，卡哥这个图真的很生动
   

class Solution {
public:int rob(TreeNode* root) {vector<int> result = robTree(root);return max(result[0], result[1]);}vector<int> robTree(TreeNode* cur) {if (cur == nullptr) return {0, 0}; // 没得偷vector<int> left = robTree(cur->left);vector<int> right = robTree(cur->right);// 偷cur，则不偷其左右子节点(取其左右子节点不偷自己的值)int var_cur_1 = cur->val + left[0] + right[0];// 不偷cur，不一定会偷子节点，选择收益最大的方式int var_cur_0 = max(left[0], left[1]) + max(right[0], right[1]);return {var_cur_0, var_cur_1};}
};