198. 打家劫舍

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]