213. 打家劫舍 II 动态规划 滚动数组
程序员文章站
2022-04-25 17:40:45
...
打家劫舍 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]
上一篇: 简单介绍 Java Map
下一篇: TP5 Request 请求对象