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