代码随想Day48 | 198.打家劫舍、213.打家劫舍II、337.打家劫舍III

这一题用动态规划五步：

1. dp[i]：到位置i，获得的最大金额；

2. 递推：当前位置偷：dp[i-2]+nums[i]；当前位置不偷：dp[i-1]；dp[i]=max(偷，不偷)；

3. 初始化：dp[0]=num[0]， dp[1] = max(num[0],num[1])；

4. 遍历顺序：从前到后

详细代码：

class Solution {
public:
    int rob(vector<int>& nums) {
        //dp[i]:到达i位置时，最大的金额
        if(nums.size()==1) return nums[0];
        if(nums.size()==2) return max(nums[0],nums[1]);
        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-2]+nums[i],dp[i-1]);
        }
        return dp[nums.size()-1];

    }
};

213.打家劫舍II??

打家劫舍2，我的思路就是基于原有的打家劫舍，把数组分为两个线性，一个只考虑头，一个只考虑尾，进行一遍从头开始到倒数第二个的遍历和另一边从第二个元素开始到最后的遍历，最后再取两个中的最大值，详细代码如下：

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]);
        if(nums.size()==3) return max(nums[0],max(nums[1],nums[2]));

        vector<int>dp1(nums.size(),0);
        vector<int>dp2(nums.size(),0);
        dp1[0]=nums[0],dp1[1]=max(nums[0],nums[1]);
        for(int i=2;i<nums.size()-1;i++)
        {
            dp1[i]=max(dp1[i-2]+nums[i],dp1[i-1]);
        }
        dp2[1]=nums[1],dp2[2]=max(nums[1],nums[2]);
        for(int i=3;i<nums.size();i++)
        {
            dp2[i]=max(dp2[i-2]+nums[i],dp2[i-1]);
        }
        return max(dp1[nums.size()-2],dp2[nums.size()-1]);

    }
};

337.打家劫舍III??

这道题目是树形dp的思路，需要把二叉树遍历和dp结合起来：

首先从递归开始思考：(需要用后序来返回节点的最大值)

参数：返回值应该是一个数组，分别是当前节点不偷和偷的最大值；传入参数则是树节点；

结束条件：当遍历到null节点，则最大值为0；

处理逻辑：先左右递归，然后再处理当前节点的逻辑。

dp的思路：

dp[0] 当前不偷节点的最大值，dp[1]:当前偷节点的最大值

递推公式：

当前偷的最大值应该等于当前值加左孩子的不偷最大值和有孩子的不偷最大值：

dp[0] = cur->val+leftdp[0]+rightdp[0]；

当前不偷的最大值应该等于左孩子的偷取最大值加右孩子的偷取最大值：

dp[1]=max(leftdp[0],leftdp[1])+max(rightdp[0],rightdp[1])；

详细代码如下：

/**
 * 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> dfs(TreeNode*root)
    {
        if(root==nullptr) return vector<int>{0,0};//结束条件
        vector<int>l = dfs(root->left);
        vector<int>r = dfs(root->right);
        int val1 = root->val+l[0]+r[0];//当前节点偷
        int val2 = max(l[0],l[1])+max(r[0],r[1]); //当前不偷
        return vector<int>{val2,val1};
    }
    int rob(TreeNode* root) {
        vector<int>dp(2,0);
        dp = dfs(root);
        //0 不偷 1：偷
        return max(dp[0],dp[1]);
    }
};