直接用动态优化解决
先构建状态转移方程,dp[i] = max(dp[i-2]+nums[i],dp[i-1])
处理好两端,dp[0]=nums[0],dp[1]=max(nums[0],nums[1])
那么,循环就直接从2开始到len(nums)
代码呈上
class Solution: def rob(self, nums: List[int]) -> int: if not nums: return 0 n = len(nums) if n == 1: return nums[0] dp = [0]*n dp[0] = nums[0] dp[1] = max(nums[0],nums[1]) for i in range(2,n): dp[i] = max(dp[i-2]+nums[i],dp[i-1]) return dp[n-1]
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)