图片素材网站建设上海市建设工程 安全协会网站

偷某间房屋时，累积金额等于间隔前两间房的金额加上当前房的金额数；不偷时，累计金额就等于前一间房的金额数。
状态转移方程：dp[i] = max(dp[i-2]+nums[i], dp[i-1])
并且注意错误点：dp[1]有两间房时，初始值为max(nums[0], nums[1])而不是纯粹等于nums[1]

class Solution(object):def rob(self, nums):""":type nums: List[int]:rtype: int"""if len(nums) <= 1:return nums[0]if len(nums) <= 2:return max(nums[0], nums[1])dp=[]for i in range(len(nums)):dp.append("0")dp[0]=nums[0]dp[1]=max(nums[1],nums[0])for i in range(2, len(nums)):dp[i] = max(dp[i - 2]+nums[i], dp[i - 1])return dp[len(dp) - 1]