【LeetCode】﹝动态规划ி﹞ 打家劫舍（小偷的贴心利益分析师）

旧城等待， 2022-12-31 04:21 107阅读 0赞

## \[LeetCode\] 打家劫舍Ⅰ，Ⅱ，Ⅲ ##

### 文章目录 ###

*   *  \[LeetCode\] 打家劫舍Ⅰ，Ⅱ，Ⅲ
     *   *  打家劫舍Ⅰ★
         *  打家劫舍Ⅱ★★
         *  打家劫舍Ⅲ★★
         *  删除并获得点数★★

### 打家劫舍Ⅰ★ ###

[198. 打家劫舍][198.]

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

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

示例1   输入[1,2,3,1]   输出4 (1+3)
    示例2   输入[2,7,9,3,1] 输出12 (2+9+1)

【**解题思路**】题目要求不能同时偷相邻的两家，对于第i家而言，有两种状态，偷与不偷，状态值初始化dp\[0\]为nums\[0\]，因为对于第1家而言偷了才是利益最大值。对于第i家而言

*  若偷，可获得总利益为`dp[i - 2] + nums[i]`，不能偷相邻的两家，所以只能在第`i-2`家基础上偷
 *  若不偷，可获得利益为`dp[i - 1]`，即前一家获得总利益

然后更新当前状态为上述两种情况的最大值，状态转移方程如下  
 d p \[ 0 \] = n u m s \[ 0 \] , i = 0 dp\[0\] = nums\[0\],i = 0 dp\[0\]=nums\[0\],i=0

d p \[ i \] = M a x ( d p \[ i − 1 \] , d p \[ i − 2 \] + n u m s \[ i \] ) , 0 < i < n dp\[i\] = Max(dp\[i - 1\], dp\[i - 2\] + nums\[i\]), 0<i<n dp\[i\]=Max(dp\[i−1\],dp\[i−2\]\+nums\[i\]),0<i<n

下述代码中设置dp数组长度为n+2并赋值为0，这样不需要单独初始化了

class Solution:
        def rob(self, nums: List[int]) -> int:
            if not nums:
                return 0
            n = len(nums)
            dp = [0] * (n + 2) #dp[2]处开始计算，这样较为简便
            for i in range(0, n):
                dp[i + 2] = max(dp[i + 1], dp[i] + nums[i])
            return dp[-1]

### 打家劫舍Ⅱ★★ ###

[213. 打家劫舍 II][213. _ II]

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

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

示例1  nums = [2,3,2]   输出:3
    示例2  nums = [1,2,3,1] 输出:4  (1+3)

【**解题思路**】此题将打家劫舍1中增加了限制条件，首尾两家相连组成环，即首尾两家不能同时偷。同样应用上述思路

*  从第1家偷到第n-1家，即不偷第n家，获得最大利益为res1
 *  从第n家偷到第2家，即不偷第1家，获得最大利益为res2（此时可将**数组反转**，继续调用代码）
 *  然后返回上述两种情况中res1和res2的最大值即可

class Solution:
        def rob(self, nums: List[int]) -> int:
            if not nums:
                return 0
            if len(nums) == 1:
                return nums[0]
            res1 = self.rob1(nums)   #考虑第1家~第n-1家(不偷第n家)
            self.reverse(nums)       #反转数组
            res2 = self.rob1(nums)   #考虑第1家~第n-1家(反转前的第n家~第2家，不偷第1家)
            return max(res1, res2)   #返回上述两种情况的最大值
    
        #打家劫舍1代码
        def rob1(self, nums):
            n = len(nums)
            dp = [0] * (n + 1)
            for i in range(0, n - 1):
                dp[i + 2] = max(dp[i + 1], dp[i] + nums[i])
            return dp[-1]
    
        #反转数组
        def reverse(self, nums):
            n = len(nums)
            for i in range(0, (int)(n / 2)):
                nums[i], nums[n - i - 1] = nums[n - i - 1], nums[i]

### 打家劫舍Ⅲ★★ ###

[337. 打家劫舍 III][337. _ III]

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

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

输入: [3,4,5,1,3,null,1]
         3
        / \
       4   5
      / \   \ 
     1   3   1
    
    输出: 9
    解释: 小偷一晚能够盗取的最高金额 = 4 + 5 = 9.

【**解题思路**】这是一道树形动态规划题，还是类似的规则，相邻的不能同时偷，对于每个结点，我们返回一个长度为2的数组**cur\[\]**，cur\[0\]为不偷当前结点，cur\[1\]为偷当前结点。因为在考虑偷与不偷父节点时要考虑子节点的情况，即左子树`le[]`和右子树`ri[]`，所以使用**树的后序遍历**。

*  若结点为空，则返回\{0, 0\}，此过程即为初始化
 *  结点不为空，若不偷此节点，左右子树偷与不偷都不影响，则cur\[0\]为左子树偷与不偷最大值加上右子树偷与不偷最大值  
    \-即`cur[0] = max(le[0], le[1]) + max(ri[0], ri[1])`
 *  结点不为空，若偷此节点，则左右子树都不能偷，则cur\[1\]为左右子树不偷的情况相加再加上当前结点值root.val  
    \-即`cur[1] = le[0] + ri[0] + root.val`
 *  最后返回遍历到根节点的最大值，即`max(cur[0], cur[1])`

class Solution:
        def rob(self, root: TreeNode) -> int:
            return max(self.helper(root))
    
        def helper(self, root: TreeNode) -> list:
            if not root:
                return [0, 0]
            le = self.helper(root.left)       #返回左子树状态
            ri = self.helper(root.right)      #返回右子树状态
            cur = [0, 0]
            cur[0] = max(le) + max(ri)        #不偷当前结点
            cur[1] = le[0] + ri[0] + root.val #偷当前结点
            return cur

### 删除并获得点数★★ ###

[740. 删除并获得点数][740.]

【**题目**】给你一个整数数组 `nums` ，你可以对它进行一些操作。

每次操作中，选择任意一个 `nums[i]` ，删除它并获得 `nums[i]` 的点数。之后，你必须删除 所有 等于`nums[i] - 1`和 `nums[i] + 1` 的元素。

开始你拥有`0` 个点数。返回你能通过这些操作获得的最大点数。

**提示：**

*  `1 <= nums.length <= 2 * 104`
 *  `1 <= nums[i] <= 104`

【**示例**】

输入：nums = [3,4,2]
    输出：6
    解释：
    删除 4 获得 4 个点数，因此 3 也被删除。
    之后，删除 2 获得 2 个点数。总共获得 6 个点数。
    -----------------------------------------------------
    输入：nums = [2,2,3,3,3,4]
    输出：9
    解释：
    删除 3 获得 3 个点数，接着要删除两个 2 和 4 。
    之后，再次删除 3 获得 3 个点数，再次删除 3 获得 3 个点数。
    总共获得 9 个点数。

【**解题思路**】

将数组转换为每个值对应的点数之和，然后就是打家劫舍的问题了

> 参考力扣热评

class Solution:
        def deleteAndEarn(self, nums: List[int]) -> int:
            n = 10001
            mark = [0] * n
            for num in nums:
                mark[num] += num
            res = self.rob(mark)
            return res
    
        def rob(self, nums: List[int]) -> int:
            if not nums:
                return 0
            n = len(nums)
            dp = [0] * (n + 2) #dp[2]处开始计算
            for i in range(0, n):
                dp[i + 2] = max(dp[i + 1], dp[i] + nums[i])
            return dp[-1]

[198.]: https://leetcode-cn.com/problems/house-robber/
[213. _ II]: https://leetcode-cn.com/problems/house-robber-ii/
[337. _ III]: https://leetcode-cn.com/problems/house-robber-iii/
[740.]: https://leetcode-cn.com/problems/delete-and-earn/