【代码随想录算法训练营第37期 第四十五天 | LeetCode198.打家劫舍、213.打家劫舍II、337.打家劫舍III】

代码随想录算法训练营第37期 第四十五天 | LeetCode198.打家劫舍、213.打家劫舍II、337.打家劫舍III

---

一、198.打家劫舍

解题代码C++：

class Solution {
public: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];}
};

题目链接/文章讲解/视频讲解：
https://programmercarl.com/0198.%E6%89%93%E5%AE%B6%E5%8A%AB%E8%88%8D.html

---

---

二、213.打家劫舍II

解题代码C++：

class Solution {
public: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];}
};

题目链接/文章讲解/视频讲解：
https://programmercarl.com/0213.%E6%89%93%E5%AE%B6%E5%8A%AB%E8%88%8DII.html

---

---

三、337.打家劫舍III

解题代码C++：

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);}
};

题目链接/文章讲解/视频讲解：
https://programmercarl.com/0337.%E6%89%93%E5%AE%B6%E5%8A%AB%E8%88%8DIII.html