Posted on 2022-12-14 14:39
Uriel 閱讀(45)
評論(0) 編輯 收藏 引用 所屬分類:
DP 、
閑來無事重切Leet Code
給定一個數(shù)組，不可以取相鄰的數(shù)，問從中取出一些數(shù)，獲得的最大和是多少，簡單DP，狀態(tài)轉(zhuǎn)移方程：
dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]) （當(dāng)前步驟不取，或者取了上上一個數(shù)，再取當(dāng)前數(shù)）
1 #198
2 #Runtime: 19 ms (Beats 88.86%)
3 #Memory: 13.5 MB (Beats 43.78%)
4
5 class Solution(object):
6 def rob(self, nums):
7 """
8 :type nums: List[int]
9 :rtype: int
10 """
11 dp = [0] * (len(nums) + 1)
12 dp[1] = nums[0]
13 for i in range(2, len(nums) + 1):
14 dp[i] = max(dp[i - 2] + nums[i - 1], dp[i - 1])
15 return max(dp)