【LeetCode动态规划#11】打家劫舍系列题（涉及环结构和树形DP的讨论）

打家劫舍

力扣题目链接(opens new window)

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

• 示例 1：
• 输入：[1,2,3,1]
• 输出：4

解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。 偷窃到的最高金额 = 1 + 3 = 4 。

• 示例 2：
• 输入：[2,7,9,3,1]
• 输出：12 解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。 偷窃到的最高金额 = 2 + 9 + 1 = 12 。

提示：

• 0 <= nums.length <= 100
• 0 <= nums[i] <= 400

思路

由题意，我们必须隔一家偷一家，因此，偷不偷当前这家取决于上一家有没有被偷

这有很明显的dp倾向

五步走

1、确定dp数组含义

dp[i]:偷房屋i最多能得到的钱是dp[i]

2、确定递推公式

根据dp含义，遍历到当前位置时，我们可以得到两种情况：偷房屋i和不偷房屋i

（1）偷

如果偷当前的房屋i的话，那么当前偷盗总金额dp[i] = dp[i - 2] + nums[i]， 即偷了这一家和上上家

（2）不偷

如果选择不偷当前的房屋i的话，那么房屋i的上一家（即房屋i - 1）就是可以偷的了，因此dp[i] = dp[i - 1]

注意，这里如果不偷当前的房屋i，不是意味着必须偷上一家的

偷不偷某一家只取决于能不能最后得到最大的盗窃金额

综上，本题的递推公式应该是dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]);

3、初始化

由上述公式可知，递推的起点应该是dp[0]和dp[1]，所以要初始化这两玩意

结合题意想一下这两个情况出现场景

如果小偷在第一家的时候就决定偷，那就会有dp[0]，而此时dp[0]一定是nums[0]

如果小偷决定先不偷第一家，看看第二家先，那此时就会有dp[1]

而根据递推公式的含义，小偷仍然可以选择偷或不偷第二家

如果不偷，那当前的盗窃金额就维持遍历到第一家时的水平，即nums[0]

不是不偷第一家才到的第二家吗，怎么现在第二家不偷第一家反而有值了呢？

因为如果第一家不偷，看第二家还不偷的话就，最后的结果肯定不是最大的，因此如果不偷第二家就默认你偷了第一家

如果选择偷，那就更新盗窃金额为nums[1]

上述两种情况，选择金额最大的情况作为dp[1]，即dp[1] = max(nums[0], nums[1]);

4、遍历顺序

因为dp[i]由dp[i - 2]和dp[i - 1]推导得到，所以要从前向后遍历

代码

class Solution {
public:
    int rob(vector<int>& nums) {
        //处理异常：当数组只有一个数或0个数
        if (nums.size() == 0) return 0;
        if (nums.size() == 1) return nums[0];
        //创建dp数组
        vector<int> dp(nums.size(), 0);
        //初始化
        dp[0] = nums[0];
        dp[1] = max(nums[0], nums[1]);
        //遍历dp数组
        for(int i = 2; i < nums.size(); ++i){
            dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]);
        }
        return dp[nums.size() - 1];
    }
};

打家劫舍II（环结构）

力扣题目链接(opens new window)

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。

给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，能够偷窃到的最高金额。

示例 1：

输入：nums = [2,3,2] 输出：3 解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。

示例 2： 输入：nums = [1,2,3,1] 输出：4 解释：你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。偷窃到的最高金额 = 1 + 3 = 4 。

示例 3： 输入：nums = [0] 输出：0

提示：

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 1000

思路

这里题目将数组改成"环"结构了，因此会多出以下情况：

（1）情况1：不偷首尾

nums[i]:[1, 6, 1, 9, 1]
            -------

因为相邻的不让偷，在环中，首尾也是相邻的，因此也不能偷

（2）情况2：不偷第一家

nums[i]:[1, 6, 1, 9, 1]
            ----------

不偷第一家就可以规避环结构带来的相邻问题

（3）情况3：不偷最后一家

nums[i]:[1, 6, 1, 9, 1]
         ----------

同理，不偷最后一家也行

综上所述，实际上情况2、3已经解决了情况1的问题（即包含了情况1），所以只需考虑后两个即可

其余部分与第一题一致（核心递推部分一致）

代码

class Solution {
private://与上题一致的处理，这里的遍历区间需要自行给出
    int robDeal(vector<int>& nums, int start, int end){
        //处理异常：遍历区间相等，说明只有一个元素，返回该元素
        if(start == end) return nums[start];

        //定义dp数组
        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]);//注意严格按照dp数组含义来写
        }
        return dp[end];
    }
public:
    int rob(vector<int>& nums) {
        //异常处理
        if(nums.size() == 0) return 0;
        if(nums.size() == 1) return nums[0];

        //调用抢劫函数，计算情况2、3下的盗窃金额，选大的作为结果
        int robRes2 = robDeal(nums, 1, nums.size() - 1);//情况2：不偷第一家
        int robRes3 = robDeal(nums, 0, nums.size() - 2);//情况3：不偷第最后一家

        return max(robRes2, robRes3);
    }
};

打家劫舍III（树形DP）

力扣题目链接(opens new window)

在上次打劫完一条街道之后和一圈房屋后，小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为“根”。 除了“根”之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。

计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。

思路

本题为树形DP，本质上是在遍历树结构的过程中计算状态转移，因此解题过程是遵循二叉树的解题步骤

这里的状态是什么？其实就是节点上的状态，即偷当前节点，或者不偷当前节点

每个节点都有一个长度为2的数组来保存偷或不偷后续节点所得到的最大金钱

三步走

1、确定递归函数的返回值与参数

因为要求出一个节点在 偷 与 不偷 两个状态下得到的金钱，所以要返回一个长度为2的数组

class Solution {
private:
    vector<int> robTree(TreeNode* cur){
        
    }
public:
    int rob(TreeNode* root) {

    }
};

这个数组就是dp数组

其含义是：[不偷之后节点所得到的最大金钱数， 偷之后节点所得到的最大金钱数]

2、确定终止条件

与常规遍历二叉树类似，我们遇到空节点就返回（注意是空节点而不是叶子节点，叶子节点本身有值）

怎么返回？当然是返回[0, 0]，空节点偷不偷都没有值

class Solution {
private:
    vector<int> robTree(TreeNode* cur){//确定递归函数返回值和参数
        //确定终止条件
        if(cur == NULL) return vector<int, int>{0, 0};
        
    }
public:
    int rob(TreeNode* root) {

    }
};

这相当于dp数组的初始化

因为树顶部的状态是由下面的子树传递上来的，因此当遍历到叶子节点之后的空节点，说明到二叉树的底部了，此时就是dp[0,0]

题外话：花括号初始化

在c++中进行初始化，{}和()有什么区别？

{}通常被称为花括号初始化，可以用于各种类型的初始化，包括基本类型和自定义类型，例如：

• 初始化int类型：int x{0};
• 初始化自定义类型：std::vector vec{1, 2, 3};

而()则是用于调用函数或构造函数的括号，例如：

• 调用函数：foo(1, "hello");
• 构造函数：std::pair<int, std::string> p(1, "hello");

对于vector{0, 0}的情况，{}被视为列表初始化vector，构造一个包含0和0两个元素的vector对象。而如果使用()，则会被视为调用vector的构造函数，需要指定vector的大小和默认值，例如：

• std::vector vec(2, 0);

这将创建一个包含2个元素且每个元素的值都为0的vector对象。

3、确定遍历顺序

因为本层节点状态需要靠其后的子节点的状态来确定，相当于要先遍历左右节点再遍历中间节点

该顺序即后序遍历

通过递归左节点，得到左节点偷与不偷的金钱。

通过递归右节点，得到右节点偷与不偷的金钱。

class Solution {
private:
    vector<int> robTree(TreeNode* cur){//确定递归函数返回值和参数
        //确定终止条件
        if(cur == NULL) return vector<int, int>{0, 0};
        
        //调用递归函数
        vector<int> left = robTree(cur->left);//左
        vector<int> right = robTree(cur->right);//右  
    }
public:
    int rob(TreeNode* root) {

    }
};

4、处理单层递归逻辑

通过递归，我们得到了当前节点的子节点的偷与不偷的最大金钱情况

于是要开始计算当前节点的两个状态

(1)偷当前节点

如果选择偷当前节点，那么其左右子节点就不能再偷了，这件事怎么表示呢？就是选择左右子节点的数组中，不偷后续节点所得到的数组值

即：val1 = cur->val + left[0] + right[0]; （当前节点的值+左子节点的不偷值+右子节点的不偷值）

(2)不偷当前节点

如果不偷当前节点，那就可以去偷其左右子节点

注意，这里的偷是指可以选择偷而不是必须偷，如果不偷总金额更大，那就不偷

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

计算完毕上述状态后，当前节点的数组中就记录了[val1, val2]，分别是：偷当前节点得到的最大金钱，不偷当前节点得到的最大金钱

class Solution {
private:
    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);//右
        
        //处理单层逻辑（中）
        int val1 = cur->val + left[0] + right[0];//偷
        int val2 = max(left[0], left[1]) + max(right[0], right[1]);//不偷
        
        return {val2, val1};
        
    }
public:
    int rob(TreeNode* root) {

    }
};

基于树的推导

代码

主函数中调用递归函数求根节点的dp数组，选值最大的情况返回即可

class Solution {
private:
    vector<int> robTree(TreeNode* cur){//确定递归函数返回值和参数
        //确定终止条件
        // if(cur == NULL) return vector<int, int>{0, 0};
        if(cur == NULL) 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 {val2, val1};
        
    }
public:
    int rob(TreeNode* root) {
        vector<int> res = robTree(root);
        return max(res[0], res[1]);
    }
};

坑：关于递归函数返回值顺序

为什么在robTree返回时需要以{不偷，偷}（即{val2, val1}）的顺序返回，而{val1, val2}则会导致结果错误？

顺一下，在处理单层逻辑时，我们是不是需要计算两个值，一个是偷当前节点的最优解，另一个是不偷当前节点的最优解

假设当前节点是A，其左右子节点分别为BC

如果我们令递归函数的返回值顺序为{不偷，偷}，即先返回不偷当前节点的最优解

那么，在使用BC的dp值计算A的dp值时，就可以直接使用BC的"不偷最优解"进行计算，从而马上得到节点A的"不偷最优解"

相反，如果此时先返回的是偷当前节点的最优解，由于不能同时偷相邻的节点，还需要使用子节点不偷的最优解来计算当前的"偷最优解"

即在先返回"偷最优解"的情况下，如果要使用左右子节点BC的dp值来计算节点A的dp值的话，还要先用BC的子节点的"不偷最优解"来计算BC的"偷最优解"（因为你公式里面就是这么定义的），于是导致了一个死循环，就卡在这了，直到最后的子节点把"不偷最优解"算完才会回到BC处计算A，然后之前暂存的节点dp数组值又会在下次计算中消失，导致全部乱掉。

这就有可能漏掉一些最优解的情况（或者全错）