198. 打家劫舍

題目

動態(tài)規(guī)劃，dp[i]表示nums[:i]這段數(shù)組小偷能偷多少錢。狀態(tài)轉(zhuǎn)移方程為：
dp[i] = max(dp[i-1],dp[i-2]+nums[i])
看下代碼，注意狀態(tài)轉(zhuǎn)移方程只與i前兩個dp元素有關(guān)。

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]