代码随想录算法训练营day45

题目：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。