代码随想录算法训练营day45

思路：本题以前没有见过，直接用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];}
};

思路：本题和上题的区别是第一个和最后一个相邻，还是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>=1vector<int> dp(end-begin+1,0);//长度至少为2dp[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>=1return 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];}
};

思路：本题首先考虑的是二叉树的遍历，由于需要返回偷的数量，故只能后序遍历，从下往上逐渐返回金额。首先是暴力方法，如果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。