198. 打家劫舍
动态规划,dp[i]表示nums[:i]这段数组小偷能偷多少钱。状态转移方程为:
dp[i] = max(dp[i-1],dp[i-2]+nums[i])
看下代码,注意状态转移方程只与i前两个dp元素有关。
class Solution:
def rob(self, nums: List[int]) -> int:
numslen = len(nums)
if numslen==0:
return 0
if numslen<3:
return max(nums)
dp = [0] * numslen
dp[0] = nums[0]
dp[1] = max(nums[0],nums[1])
for i in range(2,numslen):
dp[i] = max(dp[i-1],dp[i-2]+nums[i])
return dp[-1]