代码随想录算法训练营第五十天|198.打家劫舍、213.打家劫舍II、337.打家劫舍III

代码随想录算法训练营第五十天

198.打家劫舍

题目链接：198.打家劫舍

1. 确定dp数组以及下标的含义：dp[i]：考虑下标i（包括i）以内的房屋，最多可以偷窃的金额为dp[i]。
2. 确定递推公式：max(dp[i - 1], dp[i - 2] + nums[i]);，不偷当前节点和偷当前节点哪个获利最大就取哪个
3. dp数组如何初始化：dp[0]=nums[0]，只有一个必须偷。dp[1]=max(nums[0],nums[1])一共2个元素，只能偷一个最大的
4. 确定遍历顺序：从前向后遍历。
5. 打印dp数组。

class Solution {
public:
    int rob(vector<int>& nums) {
        if (nums.size() == 1)
            return nums[0];
        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 - 1], dp[i - 2] + nums[i]);
        }
        return dp[nums.size() - 1];
    }
};

---

213.打家劫舍II

题目链接：213.打家劫舍II
偷第一家就不能偷最后一家，偷最后一家就不能偷第一家，分别将两种状态求出，再从二者之间找最大值。两种情况分别可以用上题方法求解。

class Solution {
public:
    int Rob(vector<int>& nums,int start, int end){
        if(start==end)return nums[start];
        vector<int> dp(nums.size(), 0);
        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 - 1], dp[i - 2] + nums[i]);
        }
        return dp[end];
    }
    int rob(vector<int>& nums) {
        if(nums.size()==1)return nums[0];
        int first = Rob(nums,0,nums.size()-2);
        int last = Rob(nums, 1, nums.size()-1);
        return max(first,last);
    }
};

---

337.打家劫舍III

题目链接：337.打家劫舍III
dp数组表示，每个节点偷当前节点和不偷当前节点可以取得的最大价值。要求当前节点值需要知道左右节点的值，所以是后序遍历。最后再偷根节点和不偷根节点之间取一个最大值即可。

/**
 * 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> Rob(TreeNode* cur){
        if(cur==nullptr)return {0,0};
        vector<int> left = Rob(cur->left);
        vector<int> right = Rob(cur->right);
        vector<int>dp(2);//定义一个dp数组dp[0]表示当前节点不偷可以获得的最大金币,dp[1]表示偷当前节点可以获得的最大金币
        dp[0] = max(left[0],left[1])+max(right[0],right[1]);//不偷当前节点，那它的子节点可以选择偷或者不偷，左子偷不偷选最大的+右子偷不偷选最大的
        dp[1] = left[0]+right[0]+cur->val;//偷当前节点，左右子都不能偷，所以等于左不偷+右不偷+当前节点的值
        return dp;
    }
    int rob(TreeNode* root) {
        return max(Rob(root)[0],Rob(root)[1]);

    }
};

---