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

LeetCode 198.打家劫舍

题目链接：198.打家劫舍

踩坑：很多坑，自动把它当作背包问题了，但其实这就是一个普通的动态规划题目，背包问题本质上是一个二维问题，只是可以简化成一维，想要抽象为背包问题首先就是要明确背包大小，物品重量，物品价值。而本题的dp数组的含义是dp[i]:[0, i]家能偷到的最大价值，其中并不涉及到背包大小。

思路：

1. dp数组含义：dp[i]：[0, i]家能偷到的最大价值
2. 递推公式：dp[i] = max(dp[i - 2] + nums[i], dp[i-1])
3. 初始化：dp[0] = nums[0]; dp[1] = max(nums[0], nums[1]);
4. 遍历顺序：从小到大

代码：

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]);
        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];
    }
};

LeetCode 213.打家劫舍II

题目链接：213.打家劫舍II

踩坑：真给卡哥说中了，一有环就不知道从哪里开始，哪里结束。

思路：首尾相接带来的变化就是首尾只能选择一个或者都不选，一共三种情况。然而首尾只选其一包含了二者都不选的情况，所以只需要分别计算不选头，不选尾的两种情况并取最大即可。

代码：

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]);
        vector<int> dp(nums.size()-1, 0);
        dp[0] = nums[0];
        dp[1] = max(nums[0], nums[1]);
        for(int i = 2; i < nums.size()-1; i++)
        {
            dp[i] = max(dp[i-1], dp[i-2]+nums[i]);
        }
        int result1 = dp[nums.size()-2];
        dp[0] = nums[1];
        dp[1] = max(nums[2], nums[1]);
        for(int i = 2; i < nums.size()-1; i++)
        {
            dp[i] = max(dp[i-1], dp[i-2]+nums[i+1]);
        }
        int result2 = dp[nums.size()-2];
        return max(result1, result2);
    }
};

LeetCode 337.打家劫舍III

题目链接：337.打家劫舍III

踩坑：想到了暴力解法，但是超时了。。。（苦呀西

思路：关键在于dp数组的定义，在暴力解法中递归函数的返回值是该节点能偷到的最大值。举例节点A返回从该节点出发能偷到的最大值，B是其父节点。如果从B出发，想知道不偷A能得到的最大值就不得不重新遍历A的子树，超时也是因为大量这样的重复计算。所以，如果节点返回的是一个数组，里面有从该节点出发，偷该节点能得到的最大值与不偷该节点能得到的最大值的话，就可以解决这个问题。

代码：

/**
 * 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> tracking(TreeNode* root)
    {
        if(root == nullptr) return vector<int>{0, 0};

        vector<int> left = tracking(root->left);
        vector<int> right = tracking(root->right);
        int val1 = max(left[0], left[1]) + max(right[0], right[1]);
        int val2 = left[0] + right[0] + root->val;
        return vector<int>{val1, val2};
    }
    int rob(TreeNode* root) {
        vector<int> result = tracking(root);
        return max(result[0], result[1]);
    }
};