动态规划

dp可以解决的问题 （1）最值（2）方案数 （3）可行性
dp的方向性 ：坐标型动态规划，前缀型动态规划
dp[坐标] = 行走到这个坐标的最优值
dp[i] max{= dp[i-2] + a[i]
= dp[i-3] .
...
= dp[0]}
1.打劫房屋

class Solution:
    def rob(self, nums: List[int]) -> int:
        # 空间优化 动态规划
        if not nums:
            return 0
        n = len(nums)
        if n == 1:
            return nums[0]
        # a 是dp[i-2], b 是 dp[i-1]
        a , b = 0, nums[0]
        for i in range(1,n):
            dp = max(a + nums[i], b)
            a = b
            b = dp
        return dp