Posted on 2022-12-14 18:05
Uriel 閱讀(40)
評論(0) 編輯 收藏 引用 所屬分類:
DP 、
閑來無事重切Leet Code
第198題的加強版，
給定一個數(shù)組，這些數(shù)組組成一個圈，不可以取相鄰的數(shù)，問從中取出一些數(shù)，獲得的最大和是多少
就以第一個數(shù)為起始數(shù)，分可選第一個數(shù)（這樣最后一個數(shù)就不能選，dp到倒數(shù)第二個數(shù)為止）和不選第一個數(shù)（這樣最后一個數(shù)可選，dp到最后一個數(shù)為止）兩次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)