打家劫舍

1、题目

图1

2、题解

动态规划

设置状态数组，每个位置能抢到的最多钱等于\(max(前一屋能偷到的最多前，再前一屋偷到的最多钱+目前该屋能偷到钱)\)

class Solution:
    def rob(self, nums: List[int]) -> int:
        if len(nums)<2:
            return nums[0]
        dp = [0]*len(nums)
        dp[0] = nums[0]
        dp[1] = max(nums[0],nums[1])
        for i in range(2,len(nums)):
                dp[i] = max(dp[i-1],nums[i]+dp[i-2])      
        return max(dp)

空间优化：用两个指针来记录偷盗的金额

def rob(self, nums: List[int]) -> int:
    prev = 0
    curr = 0
    
    # 每次循环，计算“偷到当前房子为止的最大金额”
    for i in nums:
        # 循环开始时，curr 表示 dp[k-1]，prev 表示 dp[k-2]
        # dp[k] = max{ dp[k-1], dp[k-2] + i }
        prev, curr = curr, max(curr, prev + i)
        # 循环结束时，curr 表示 dp[k]，prev 表示 dp[k-1]

    return curr