LeetCode 198 打家劫舍
题目链接：https://leetcode.cn/problems/house-robber/
思路：
dp数组的含义
dp[i]表示前i个房间（包括第i个房间）所能偷到的最大金额
递推公式
有两种情况：
1、偷了第i个房间
那么此时第i-1个房间肯定是不偷的，所以
2、没有偷第i个房间
那么有可能偷了第i-1个房间，所以此时
因为求的是最大金额，所以二者要求最大值
初始化
由递推公式可知，显然需要初始化dp[0]和dp[1]，dp[0]=nums[0]，dp[1]=max(nums[0],nums[1])
遍历顺序
因为dp[i]依赖于dp[i-1]和dp[i-2]，所以必然是从前往后遍历
代码：
class Solution {
public:int rob(vector<int>& nums) {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]);}for(int i = 0; i < dp.size(); i++)cout << dp[i] << " ";cout << endl;return dp[nums.size() - 1];}
};总结
自己写的时候，dp数组的含义定义错误了
LeetCode 213 打家劫舍II
题目链接：https://leetcode.cn/problems/house-robber-ii/
思路：
本题要分成两种情况来讨论：
1、考虑包含头元素，不包含尾元素
2、考虑包含尾元素，不包含头元素
最后求两种情况的最大值即为答案。
注：“考虑"不代表必须要选，例如情况二，虽然是考虑包含尾元素，但不一定要选尾部元素！ 对于情况二，取nums[1] 和 nums[3]就是最大的。
代码：
class Solution {
public:int rob(vector<int>& nums) {if(nums.size() == 1) return nums[0];if(nums.size() == 2) return max(nums[0], nums[1]);int result1 = robRange(nums, 0, nums.size() - 2); // 不包含尾元素的情况int result2 = robRange(nums, 1, nums.size() - 1); // 不包含头元素的情况return max(result1, result2);}int robRange(vector<int>&nums, int start, int end){vector<int>dp(nums.size(), 0);dp[start] = nums[start];dp[start + 1] = max(nums[start],nums[start + 1]);for(int i = 2; i <= end; i++){dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]);}return dp[end];}};总结
学会了数组环形要如何解决
LeetCode 337 打家劫舍III
题目链接：https://leetcode.cn/problems/house-robber-iii/
思路：
dp数组的含义
dp[0]代表不偷该节点时的最大金额
dp[1]代表偷该节点时的最大金额
遍历顺序
首先明确的是使用后序遍历。 因为要通过递归函数的返回值来做下一步计算。
通过递归左节点，得到左节点偷与不偷的金钱。
通过递归右节点，得到右节点偷与不偷的金钱。
单层递归逻辑
1、不偷当前节点
那么此时就可以选择偷和不偷左右节点。
2、偷当前节点
那么就是选择不偷左右子树
举例推导
代码：
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
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 vector<int>(2, 0);// 后续遍历vector<int>leftdp = robTree(cur -> left);vector<int>rightdp = robTree(cur -> right);int val0 = max(leftdp[0], leftdp[1]) + max(rightdp[0], rightdp[1]);int val1 = cur->val + leftdp[0] + rightdp[0];return vector<int>{val0, val1};}
};总结
dp和树结合的一道题
今日总结：
三道打家劫舍的题目对应了普通数组情况，环形情况和树形情况。其中环形情况和树形情况需要多加练习和理解。
