【Leetcode Python】
偷某间房屋时,累积金额等于间隔前两间房的金额加上当前房的金额数;不偷时,累计金额就等于前一间房的金额数。
状态转移方程: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]