题目：198.打家劫舍、213.打家劫舍II、337.打家劫舍III
参考链接：代码随想录
198.打家劫舍
思路：本题以前没有见过，直接用dp五部曲试试：dp数组，dp[i]表示考虑下标i之前的房屋，可以偷盗的最大数量；递推公式，这里需要仔细考虑，当房屋i加入时，能不能偷i取决于i-1有没有被偷，如果偷了，则dp[i]=dp[i-1]，如果没偷，dp[i]=dp[i-2]+nums[i]，注意在计算过程中我们不知道i-1是否被偷了，故取max即可；初始化，由递推公式知需要初始化dp[0]和dp[1]，dp[0]=nums[0]，dp[1]=max(dp[0],dp[1])，其他初始化为0；遍历顺序，顺序遍历即可；举例略。时间复杂度O(n)。
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];
}
};
213.打家劫舍II
思路：本题和上题的区别是第一个和最后一个相邻，还是dp五部曲：dp数组，dp[i]表示考虑前i个房屋，能偷的最大数量；递推公式，首先要考虑是不是房屋n-1，当不是的时候，和上题一样，如果不偷i，则dp[i-1]，如果偷i，则dp[i-2]+nums[i]，当是i==n-1房屋的时候，这时还要考虑房屋0，如果不偷n-1，则dp[i-1]，如果偷n-1，则0不能偷，i-1也不能偷，但这里的dp推导则卡住了，故直接从0开始考虑是考虑不出来的。我们想想分类讨论，本题的问题是成环，则分解成不成环的情况，第一种情况为不偷0，第二种情况为不偷n-1，这两个不可能全偷，故分这两类讨论就能覆盖全部情况了（A：偷0；B：偷n-1。已知不可能A and B，故剩下的情况就只有!A or !B）。分类讨论后，问题就变成了上题，在写代码的时候可以把上题单独抽象成一个函数。时间复杂度O(n)。
class Solution {
public:
int robRange(vector<int> &nums,int begin,int end){//默认end-begin>=1
vector<int> dp(end-begin+1,0);//长度至少为2
dp[0]=nums[begin];
dp[1]=max(nums[begin],nums[begin+1]);
for(int i=2;i<end-begin+1;i++){
dp[i]=max(dp[i-1],dp[i-2]+nums[begin+i]);//注意这里的dp[i]表示begin往后数i个
}
return dp[end-begin];
}
int rob(vector<int>& nums) {
if(nums.size()==1){
return nums[0];
}
if(nums.size()==2){
return max(nums[0],nums[1]);
}//首先排除长度1和2后，长度至少为3，这样去掉头或者尾，剩下的至少有2，end-begin>=1
return max(robRange(nums,0,nums.size()-2),robRange(nums,1,nums.size()-1));
}
};
标答中将长度为2没有单独考虑，放在了子函数的begin==end中：
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];
}
};
337.打家劫舍III
思路：本题首先考虑的是二叉树的遍历，由于需要返回偷的数量，故只能后序遍历，从下往上逐渐返回金额。首先是暴力方法，如果root为空，则返回0，否则考虑其两个孩子，如果都为空，则返回root->val。主要考虑偷不偷root的情况，如果偷，则其左右孩子都不能偷，分别对其左右孩子的孩子偷（孙子），如果不偷root，则直接偷左右孩子。暴力方法超时。考虑记忆化递归的方法，使用一个map保存计算结果，当后序递归时用到了已经计算过的结果，可以直接使用。时间复杂度O(n)。
class Solution {
public:
unordered_map<TreeNode*,int> mp;
int rob(TreeNode* root) {
if(!root){
return 0;
}
if(!root->left && !root->right){
return root->val;
}
if(mp[root]){
return mp[root];//存过，直接返回结果
}
int val1=root->val;
if(root->left){//偷了root，左孩子不能再偷了
val1+=rob(root->left->left)+rob(root->left->right);
}
if(root->right){
val1+=rob(root->right->left)+rob(root->right->right);
}
int val2=rob(root->left)+rob(root->right);
mp[root]=max(val1,val2);
return max(val1,val2);
}
};
然后考虑dp方法，本题和之前的题目都不一样，本题是树形dp的入门题目。dp实际上就是状态转移，需要用一个状态转移容器记录状态的变化，本题使用一个长度为2的数组，记录当前节点偷与不偷的最大金钱。考虑递推三部曲和dp五部曲：首先是递推参数和返回值，参数为当前节点，返回值为dp数组，dp[0]和dp[1]分别记录不偷和偷该节点得到的最大金钱，对于本题的树形dp，dp数组只有两个数，状态变化过程存在递归栈中；然后是终止条件，当遇到空节点，偷或不偷都是0，这也相当于初始化了dp数组；然后是遍历顺序，使用后序遍历，因为需要根据孩子的结果计算root；最后是单层递归逻辑，偷当前节点，则左右孩子不能偷，val1=cur->val+left[0]+right[0]，如果不偷当前节点，左右孩子都能偷或者不偷，选最大的，val2=max(left[0]+left[1])+max(right[0]+right[1])，求出当前状态即为{val2,val1}。时间复杂度O(n)。
/**
* 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:
vector<int> robTree(TreeNode* cur){
if(!cur){
return vector<int>{0,0};//这也完成了初始化
}
vector<int> left=robTree(cur->left);
vector<int> right=robTree(cur->right);
int val1=cur->val+left[0]+right[0];
int val2=max(left[0],left[1])+max(right[0],right[1]);
return vector<int>{val2,val1};
}
int rob(TreeNode* root) {
vector<int> ans=robTree(root);
return max(ans[0],ans[1]);
}
};
本题一定要牢记，主要需要了解树形dp的思路，重点在将dp数组隐含在递归遍历中，之前的dp题目都没有涉及到递归，利用返回值初始化dp数组，在后序遍历数的过程中也就将dp数组的状态转移过程传递到了root。