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
网友评论