欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

213. 打家劫舍 II 动态规划 滚动数组

程序员文章站 2022-04-25 17:40:45
...

打家劫舍 II

213. 打家劫舍 II 动态规划 滚动数组

二维动态规划

dp[i][0] :表示在不选第一个元素的情况下,,当到第i个元素时的最大金额
dp[i][1] :表示在选择第一个数的情况下,当到第i个元素时的最大金额
初始化状态:
dp[0][0] = 0 # 不选第一个元素
dp[0][1] = nums[0] # 选第一个元素
dp[1][0] = max(dp[0][0], 0 + nums[1]) # 不选, 继承前一个dp[i-1][0]的值, 或者 前两个dp[-1][0] + nums[1] ,dp[-1][0] 可认为为0
dp[1][1] = max(dp[0][1], 0 + nums[1]) # 选, 继承前一个dp[i-1][1]的值, 或者 前两个dp[-1][1] + nums[1], dp[-1][1] 可认为为0
状态转移:
dp[i][0] = max(dp[i-1][0], dp[i-2][0] + nums[i]) # dp[i][0] 只能继承dp[i-1][0] 的值,不能继承dp[i-1][1] 的值,否则与状态的本身意义矛盾
dp[i][1] = max(dp[i-1][1], dp[i-2][1] + nums[i]) # dp[i][1] 只能继承dp[i-1][1] 的值,不能继承dp[i-1][0] 的值,否则与状态的本身意义矛盾
class Solution:
    def rob(self, nums: List[int]) -> int:
        length = len(nums)
        if length == 0:
            return 0
        if length == 1:
            return nums[0]
        dp = [[0]*2 for _ in range(2)]
        dp[0][0] = 0
        dp[0][1] = nums[0]
        dp[1][0] = max(dp[0][0], 0 + nums[1])
        dp[1][1] = max(dp[0][1], 0 + nums[1])
        for i in range(2, length):
            dp[i%2][0] = max(dp[(i-1)%2][0], dp[(i-2)%2][0] + nums[i])
            dp[i%2][1] = max(dp[(i-1)%2][1], dp[(i-2)%2][1] + nums[i]) if i < length-1 else dp[(i-1)%2][1]
        return max(dp[(length-1)%2][0], dp[(length-1)%2][1])

对于dp[i%2][1] = max(dp[(i-1)%2][1], dp[(i-2)%2][1] + nums[i])i = length - 1时,由于取不到最后一个元素,所以代码额外增加了一个判断条件

也可以理解为:分别在两种情况的简答问题: 及[0,end-1] 和[1,end] 两种简单情况下的两个问题。

class Solution:
    def rob(self, nums: [int]) -> int:
        def my_rob(nums):
            cur, pre = 0, 0
            for num in nums:
                cur, pre = max(pre + num, cur), cur
            return cur
        return max(my_rob(nums[:-1]),my_rob(nums[1:])) if len(nums) != 1 else nums[0]