LeetCode 198 打家劫舍

直接用动态优化解决

先构建状态转移方程，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]