本文主要是介绍代码随想录算法训练营day47|第九章 动态规划part09：198.打家劫舍、213.打家劫舍II、337.打家劫舍III，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
目录
打家劫舍是DP解决的经典题目，今天就是打家劫舍的一天，这个系列不算难，大家可以一口气拿下。
198.打家劫舍
213.打家劫舍II
337.打家劫舍III
198.打家劫舍
视频讲解：动态规划，偷不偷这个房间呢？| LeetCode：198.打家劫舍_哔哩哔哩_bilibili
代码随想录
首先，dp[i]表示考虑下标i（包括i）以内的房屋，最多可以偷窃的金额。如果偷了当前房间，那么当前的金额就是偷前i-2个房间得到的最大金额+本房间金额，如果没偷，那么当前金额就是偷前i-1个房间得到的最大金额，那么递推公式就很明确了，dp[i] = max(dp[i - 2] + nums[i], dp[i - 1])。因为递推公式涉及到前两个dp数组值，所以0、1下标处必须提前初始化好，设置dp[0]为nums[0]（只有一个房间可以偷，那没顾虑直接偷）、dp[1]为nums[0]和nums[1]中较大者（只有两个房间可以偷，那只能偷最大金额的那个）。
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
视频讲解：动态规划，房间连成环了那还偷不偷呢？| LeetCode：213.打家劫舍II_哔哩哔哩_bilibili
代码随想录
这道题加上了一个房间成环的设定，那就没办法直接让某个房间作为开始的房间然后沿路偷下去，但是可以将起始点单独拎出来考虑，也就是划分成都偷房间0和不偷房间0两种情况来考虑，这样拿走了0，就让剩下的没法成环，这样就可以用第一道题的思路来解决。如果偷房间0，那就偷的范围就变成了下标0到n-2，不偷房间0，范围就变成下标1到n-1，找出这两种情况的最大值。
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);}// 198.打家劫舍的逻辑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];}337.打家劫舍III
视频讲解：动态规划，房间连成树了，偷不偷呢？| LeetCode：337.打家劫舍3_哔哩哔哩_bilibili
代码随想录
记忆化递归——
直接递归是超时的，所以用map来记录一下当前节点的最大值，来防止对已经找到最大值的节点重复找最大值，但实际上还是有局限，基本上想要得到最大值就得要临时计算很多值。
class Solution {
public:unordered_map<TreeNode* , int> umap; // 记录计算过的结果int rob(TreeNode* root) {if (root == NULL) return 0;if (root->left == NULL && root->right == NULL) return root->val;if (umap[root]) return umap[root]; // 如果umap里已经有记录则直接返回// 偷父节点int val1 = root->val;if (root->left) val1 += rob(root->left->left) + rob(root->left->right); // 跳过root->leftif (root->right) val1 += rob(root->right->left) + rob(root->right->right); // 跳过root->right// 不偷父节点int val2 = rob(root->left) + rob(root->right); // 考虑root的左右孩子umap[root] = max(val1, val2); // umap记录一下结果return max(val1, val2);}
};动态规划——
这道题的动规方法是超难想到的，使用vector<int>数组作为返回值来实时记录偷与不偷这个节点得到的最大值，这样就方便多了。注意不偷当前节点的话，也不一定要偷子节点的值，还是要取左右子节点偷与不偷的最大值的加和。
class Solution {
public:int rob(TreeNode* root) {vector<int> result = robTree(root);return max(result[0], result[1]);}// 长度为2的数组，0：不偷，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};}
};这道题是树形DP的入门题目，通过这道题目大家应该也了解了，所谓树形DP就是在树上进行递归公式的推导。
所以树形DP也没有那么神秘！
只不过平时我们习惯了在一维数组或者二维数组上推导公式，一下子换成了树，就需要对树的遍历方式足够了解！
大家还记不记得我在讲解贪心专题的时候，讲到这道题目：贪心算法：我要监控二叉树！ (opens new window)，这也是贪心算法在树上的应用。那我也可以把这个算法起一个名字，叫做树形贪心。
这篇关于代码随想录算法训练营day47|第九章 动态规划part09：198.打家劫舍、213.打家劫舍II、337.打家劫舍III的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
