力扣 198. 打家劫舍

动态规划方程

状态转移: $ f(i) = max(f(i - 2) + cur, f(i - 1)) $

初始化: $dp[0]=0,dp[1]=nums[0]$

一维动态规划

def rob(nums):
    # 动态规划
    dp = [0] * (len(nums) + 1)
    dp[1] = nums[0]
    for i in range(1, len(nums)):
        dp[i + 1] = max(nums[i] + dp[i - 1],dp[i])
    return dp[-1]

空间优化动态规划

def rob(nums):
    # 动态规划
    ppre, pre, cur = 0, nums[0], 0
    for i in range(1, len(nums)):
        cur = max(nums[i] + ppre, pre)
        ppre, pre = pre, cur
    return pre