Day 48 动态规划 9

198. 打家劫舍1

代码随想录

?1. 思路

本体是非常简单的动态规划问题，dp[i]就代表0-i这些家可以抢劫到的最大金额，分两种情况进行讨论。一个是抢当前的不抢之前的，一个是不抢当前的。代码如下：

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. 打家劫舍2

代码随想录

1. 思路

这道题也很简单，分解成0～n-1以及1～n这两个区间即可，分别比较。

在实现的时候，我使用了两个额外的数组记录0～n-1以及1～n，实际上可以将打家劫舍1中的函数改编成start和end定义的，这样就不用额外分配内存了。

class Solution {
public:
    int rob(TreeNode* root) {
        vector<int> result = robTree(root);
        return max(result[0], result[1]);
    }
    // 长度为2的数组，0：不偷，1：偷
    vector<int> robTree(TreeNode* cur) {
        if (cur == NULL) return vector<int>{0, 0};
        vector<int> left = robTree(cur->left);
        vector<int> right = robTree(cur->right);
        // 偷cur，那么就不能偷左右节点。
        int val1 = cur->val + left[0] + right[0];
        // 不偷cur，那么可以偷也可以不偷左右节点，则取较大的情况
        int val2 = max(left[0], left[1]) + max(right[0], right[1]);
        return {val2, val1};
    }
};

?

337. 打家劫舍3

代码随想录

1. 思路

（1）对打家劫舍的泛化

可以看出，打家劫舍其实是在打劫和不打劫之间选择的一个问题，如果把这个选择明确，将更加规范合理。就像背包问题每个物品是一种选择一样，这里的打劫和不打劫其实就相当于背包的物品，因此可以利用二维数组。dp[i][j]分别表示这一家打劫或者不打劫的最优收益。则dp数组的更新逻辑为：

dp[0][j] (第j家打劫）= val + dp[1][j-1]

dp[1][j] (第j家不打劫）= max(dp[0][j-1], dp[1][j-1])

最后返回max(dp[0][-1], dp[1][-1])

（2）一维数组和二维数组的关系

相较于一维数组的更新逻辑：

dp[j] = max(val+dp[j-2],dp[j-1])

我们可以这样互相推导出来：

二维数组递归最优解?= max(dp[0][j] ?打劫这家, dp[1][j] ?不打劫这家)

= max(val+dp[1][j-1] ?打劫这家+不打劫上一家,?max(dp[0][j-1], dp[1][j-1]) ?打劫上一家或者不打劫上一家)

=?max(val+dp[1][j-1] 打劫这家+不打劫上一家,?dp[j-1] 上一家最优解)

=?max(val+dp[j-2] 打劫这家+上上家最优解, dp[j-1] 上一家最优解)?=?一维数组递归最优解

其中有两个假设条件：

dp[1][j-1] = dp[i-2]，不打劫上一家等价于上上家的最优解。

max(dp[0][j-1], dp[1][j-1]) = dp[j-1]，上一家打不打劫的最优解等于上一家的最优解。

（3）一维数组在多邻居时出现的问题

其中第一条假设条件在邻居不唯一的情况下出现了问题。因为这时一维dp数组无法表示唯一的上上家，而是会像二叉树一样不断膨胀。

其实，问题的根源在于，我们在只有一个邻居的时候复用了相邻这个概念。那时dp数组两个元素临近可以代表邻居关系，但如果有多个邻居，一维dp数组的前后关系代表不了邻里关系。

因此，我们必须要详细区分元素被选取与否，也就是用二维数组，加上二叉树的不断递归，这样可以实现我们的需求。

这时二维dp数组更新条件为：

val1 = val + left[1] + right[1]

val2 = max(left[0], left[1]) + max(right[0], right[1]);

最后当前节点的状态就是{val1, val2};

可以发现，这里i这个维度用二叉树进行表示了。

class Solution {
public:
    int rob(TreeNode* root) {
        vector<int> result = robTree(root);
        return max(result[0], result[1]);
    }
    // 长度为2的数组，0：不偷，1：偷
    vector<int> robTree(TreeNode* cur) {
        if (cur == NULL) return vector<int>{0, 0};
        vector<int> left = robTree(cur->left);
        vector<int> right = robTree(cur->right);
        // 偷cur，那么就不能偷左右节点。
        int val1 = cur->val + left[0] + right[0];
        // 不偷cur，那么可以偷也可以不偷左右节点，则取较大的情况
        int val2 = max(left[0], left[1]) + max(right[0], right[1]);
        return {val2, val1};
    }
};