Posted on 2022-12-14 14:39
Uriel 閱讀(50)
評論(0) 編輯 收藏 引用 所屬分類:
DP 、
閑來無事重切Leet Code
給定一個數組，不可以取相鄰的數，問從中取出一些數，獲得的最大和是多少，簡單DP，狀態轉移方程：
dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]) （當前步驟不取，或者取了上上一個數，再取當前數）
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)