数据结构算法刷题（29）动态规划
思路一：回溯：按照选和不选的判断方式，使用回溯来解决这个问题。
class Solution:
def rob(self, nums: List[int]) -> int:
n = len(nums) #数组的长度
def dfs(i):
if i<0: #到达边界条件后
return 0 #返回最大金额是0
res = max(dfs(i-1),dfs(i-2)+nums[i]) #如果选，下一次递归的就是i-2，并且要加上nums[i]的值，如果不选，下一次递归i-1。比较选或者不选的最大值并返回。
return res
res = dfs(n-1) #传入的是数组的最大下标
return res
问题：回溯使用递归，时间复杂度是指数级别的，会超时，那如何让时间降下来？
思路二：有两次相同的计算结果，那就把每个位置的计算结果保存下来，可以把时间缩短。
class Solution:
def rob(self, nums: List[int]) -> int:
n = len(nums)
cache = [-1]*n #因为每个位置一定不是负数
def dfs(i):
if i<0:
return 0
if cache[i] != -1: #当前的位置不是-1，那么这个位置被计算过，直接返回计算的结果
return cache[i]
res = max(dfs(i-1),dfs(i-2)+nums[i])
cache[i] = res #把当前位置的计算结果保存
return res
res = dfs(n-1)
return res
问题：这种方式的空间复杂度就是O(n)，如何将空间复杂度降下来：递推
思路三：我们可以确定的知道每个节点是那几个数归的结果，那把递的过程省略，直接归，也就是从下往上计算结果。
循环对数组下标有要求，所以下标从2开始。
class Solution:
def rob(self, nums: List[int]) -> int:
n = len(nums)
f = [0]*(n+2) #归的数组长度是n+2，每个数组的值是0
for i,x in enumerate(nums): #遍历nums
f[i+2] = max(f[i+1],f[i]+x) # 等同于res = max(dfs(i-1),dfs(i-2)+nums[i])
return f[n+1]
改进空间复杂度：
class Solution:
def rob(self, nums: List[int]) -> int:
n = len(nums)
f0 = f1 = 0
for i,x in enumerate(nums):
new_f = max(f1,f0+x)
f0 = f1
f1 = new_f
return f1
思路：
class Solution:
def climbStairs(self, n: int) -> int:
dp0 = 1
dp1 = 1
if n <= 1:
return 1
dp = 0
for i in range(2,n+1):
dp = dp0 + dp1
dp0 = dp1
dp1 = dp
return dp
思路：
class Solution:
def minCostClimbingStairs(self, cost: List[int]) -> int:
n = len(cost)
dp0 = 0 #第0级台阶的顶部最小花费是0
dp1 = min(cost[0],cost[1]) #第1级台阶的顶部台阶的最小花费是cost[0]或cost[1]的最小值
for i in range(2,n):
dp = min(dp1+cost[i],dp0+cost[i-1])
dp0 = dp1
dp1 = dp
return dp1