Posted on 2022-12-14 14:39
Uriel 阅读(39)
评论(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)