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& nums) {if(nums.size() == 1)    return nums[0];vectordp(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& 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&nums, int start, int end){vectordp(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) {vectorresult = robTree(root);return max(result[0], result[1]);}vector robTree(TreeNode *cur){if(cur == nullptr) return vector(2, 0);// 后续遍历vectorleftdp = robTree(cur -> left);vectorrightdp = 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{val0, val1};}
};

总结

dp和树结合的一道题

今日总结：

三道打家劫舍的题目对应了普通数组情况，环形情况和树形情况。其中环形情况和树形情况需要多加练习和理解。