0213. 打家劫舍 II

0213. 打家劫舍 II #

  • 标签:动态规划
  • 难度:中等

题目大意 #

描述:给定一个数组 numsnum[i] 代表第 i 间房屋存放的金额,假设房屋可以围成一圈,最后一间房屋跟第一间房屋可以相连。相邻的房屋装有防盗系统,假如相邻的两间房屋同时被偷,系统就会报警。

要求:假如你是一名专业的小偷,计算在不触动警报装置的情况下,一夜之内能够偷窃到的最高金额。

说明

  • $1 \le nums.length \le 100$。
  • $0 \le nums[i] \le 1000$。

示例

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

解题思路 #

思路 1:动态规划 #

这道题可以看做是「 198. 打家劫舍」的升级版。

如果房屋数大于等于 3 间,偷窃了第 1 间房屋,则不能偷窃最后一间房屋。同样偷窃了最后一间房屋则不能偷窃第 1 间房屋。

假设总共房屋数量为 size,这种情况可以转换为分别求解 [0, size - 2][1, size - 1] 范围下首尾不相连的房屋所能偷窃的最高金额,然后再取这两种情况下的最大值。而求解 [0, size - 2][1, size - 1] 范围下首尾不相连的房屋所能偷窃的最高金额问题就跟「 198. 打家劫舍」所求问题一致了。

这里来复习一下「 198. 打家劫舍」的解题思路。

1. 划分阶段 #

按照房屋序号进行阶段划分。

2. 定义状态 #

定义状态 dp[i] 表示为:前 i 间房屋所能偷窃到的最高金额。

3. 状态转移方程 #

如果房屋数大于等于 3 间,则偷窃第 i 间房屋的时候,就有两种状态:

  • 偷窃第 i 间房屋,那么第 i - 1 间房屋就不能偷窃了,偷窃的最高金额为:前 i - 2 间房屋的最高总金额 + 第 i 间房屋的金额,即 dp[i] = dp[i - 2] + nums[i]
  • 不偷窃第 i 间房屋,那么第 i - 1 间房屋可以偷窃,偷窃的最高金额为:前 i - 1 间房屋的最高总金额,即 dp[i] = dp[i - 1]

然后这两种状态取最大值即可,即状态转移方程为:dp[i] = max(dp[i - 2] + nums[i], dp[i - 1])i > 2 时。

4. 初始条件 #
  • 如果只有一间房,则直接偷这间屋子就能偷到最高金额,即 dp[0] = nums[i]
  • 如果只有两间房,那么就选择金额最大的那间屋进行偷窃,就可以偷到最高金额,即 dp[1] = max(nums[0], nums[1])
5. 最终结果 #

根据我们之前定义的状态,dp[i] 表示为:前 i 间房屋所能偷窃到的最高金额。假设求解 [0, size - 2][1, size - 1] 范围下( size 为总的房屋数)首尾不相连的房屋所能偷窃的最高金额问题分别为 ans1ans2,则最终结果为 max(ans1, ans2)

思路 1:动态规划代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution:
    def helper(self, nums):
        size = len(nums)
        if size == 1:
            return nums[0]
        if size == 2:
            return max(nums[0], nums[1])
        
        dp = [0 for _ in range(size)]
        dp[0] = nums[0]
        dp[1] = max(nums[0], nums[1])
        
        for i in range(2, size):
            dp[i] = max(dp[i - 2] + nums[i], dp[i - 1])

        return dp[size - 1]

    def rob(self, nums: List[int]) -> int:
        size = len(nums)
        if size == 1:
            return nums[0]
        
        ans1 = self.helper(nums[:size - 1])
        ans2 = self.helper(nums[1:])
        return max(ans1, ans2)

思路 1:复杂度分析 #

  • 时间复杂度:$O(n)$。一重循环遍历的时间复杂度为 $O(n)$。
  • 空间复杂度:$O(n)$。用到了一维数组保存状态,所以总体空间复杂度为 $O(n)$。
本站总访问量  次  |  您是本站第  位访问者