Posted on 2022-12-14 18:05
Uriel 阅读(25)
评论(0) 编辑 收藏 引用 所属分类:
DP 、
闲来无事重切Leet Code
第198题的加强版，
给定一个数组，这些数组组成一个圈，不可以取相邻的数，问从中取出一些数，获得的最大和是多少
就以第一个数为起始数，分可选第一个数（这样最后一个数就不能选，dp到倒数第二个数为止）和不选第一个数（这样最后一个数可选，dp到最后一个数为止）两次dp，取其中的较大值
1 #213
2 #Runtime: 20 ms (Beats 86.87%)
3 #Memory: 13.3 MB (Beats 66.70%)
4
5 class Solution(object):
6 def rob(self, nums):
7 """
8 :type nums: List[int]
9 :rtype: int
10 """
11 dp_pre1 = nums[0]
12 dp_pre2 = 0
13 dp_cur = nums[0]
14 for i in range(2, len(nums)):
15 dp_cur = max(dp_pre2 + nums[i - 1], dp_pre1)
16 dp_pre2 = dp_pre1
17 dp_pre1 = dp_cur
18 ans = dp_cur
19 dp_pre1 = 0
20 dp_pre2 = 0
21 dp_cur = 0
22 for i in range(2, len(nums) + 1):
23 dp_cur = max(dp_pre2 + nums[i - 1], dp_pre1)
24 dp_pre2 = dp_pre1
25 dp_pre1 = dp_cur
26 return max(ans, dp_cur)