0x3f第11天 动态规划课后习题

1.爬楼梯

1.最关键的一点就是得知道dfs（i）代表的什么

代表一直到台阶i的时候有多少种走法

2.这样就能得到dfs（i）=dfs（i-1）+dfs（i-2）

3.dfs（0）= 1

因为dfs（2）=2 dfs（1）=1 所以dfs（0）必须等于1

回溯代码：

时间复杂度2^n 空间复杂度n

class Solution: def climbStairs(self, n: int) -> int: def dfs(i): if i <=1: return 1 return dfs(i-1)+dfs(i-2) return dfs(n)

记忆型代码：@cache

@cache是装饰器，必须紧贴在被装饰的函数定义上方

时间复杂度n 空间复杂度n

递推型代码：

时间复杂度n 空间复杂度n

class Solution: def climbStairs(self, n: int) -> int: f = [0]*(n+1) f[0]=f[1]=1 for i in range(2,n+1): f[i]=f[i-1]+f[i-2] return f[n]

怎么创建数组f，f=【0】*（n+1），我写的是

f = [0]*n

这样会产生一个长度为n的数组，那就没有f[n]了，最大是f[n-1]，所以需要一个长度为n+1的

空间优化：

时间复杂度n 空间复杂度1

class Solution: def climbStairs(self, n: int) -> int: f0=f1=1 for i in range(n-1): newf=f0+f1 f0 = f1 f1 = newf return f1

---

---

---

2.使用最小花费爬楼梯

回溯法：

我错误的地方

if i<=1: return min(cost[0],cost[1])

i为0，或者1 的时候取什么值，读题目没读懂

你可以选择从下标为0或下标为1的台阶开始爬楼梯

结合dfs（i）的定义：到第i层台阶需要花费多少钱

所以dfs(0),dfs(1)，到第0，第1层不需要钱

时间2^n，空间n

class Solution: def minCostClimbingStairs(self, cost: List[int]) -> int: n = len(cost) def dfs(i): if i<=1: return min(cost[0],cost[1]) return min(dfs(i-1)+cost[i-1],dfs(i-2)+cost[i-2]) return dfs(n)

记忆性cache：

cache必须依附于装饰的函数

@cache是装饰器，必须紧贴在被装饰的函数定义上方

时间复杂度n 空间复杂度n

class Solution: def minCostClimbingStairs(self, cost: List[int]) -> int: n = len(cost) @cache def dfs(i): if i<=1: return 0 return min(dfs(i-1)+cost[i-1],dfs(i-2)+cost[i-2]) return dfs(n)

递推型代码：

时间复杂度n 空间复杂度n

class Solution: def minCostClimbingStairs(self, cost: List[int]) -> int: n = len(cost) f = [0]*(n+1) f[0]=f[1]=0 for i in range(2,n+1): f[i] = min(f[i-1]+cost[i-1],f[i-2]+cost[i-2]) return f[n]

空间优化：

时间复杂度n 空间复杂度1

class Solution: def minCostClimbingStairs(self, cost: List[int]) -> int: n = len(cost) f0=f1=0 for i in range(2,n+1): newf= min(f1+cost[i-1],f0+cost[i-2]) f0 = f1 f1 = newf return f1

---

---

---

3.爬楼梯Ⅱ

回溯法cache：

多了一个跳三阶，和cost计算公式，其实没啥本质区别，多计算一个dfs（2）

其实也不用

还是只需要计算 i<=0 和i = 1，计算i=2是怕 i-3的时候越界，但其实会归到i<=0的地方

min(dfs(i-1)+costs[i-1]+1,dfs(i-2)+costs[i-1]+4,dfs(i-3)+costs[i-1]+9)

class Solution: def climbStairs(self, n: int, costs: List[int]) -> int: @cache def dfs(i): if i<=0: return 0 if i==1: return costs[0]+1 return min(dfs(i-1)+costs[i-1]+1,dfs(i-2)+costs[i-1]+4,dfs(i-3)+costs[i-1]+9) return dfs(n)

递推：

自己写的代码：ac但是相比灵神冗余，但是对自己来说好理解

class Solution: def climbStairs(self, n: int, costs: List[int]) -> int: f=[0]*(n+1) f[0] = 0 f[1] = costs[0]+1 if n>1: f[2] = min(f[1]+costs[1]+1,f[0]+costs[1]+4) for i in range(3,n+1): f[i] = min(f[i-1]+costs[i-1]+1,f[i-2]+costs[i-1]+4,f[i-3]+costs[i-1]+9) return f[n]

空间优化：太冗余了，看着都想笑

主要就是对i=2的判断

class Solution: def climbStairs(self, n: int, costs: List[int]) -> int: f0 = 0 f1 = costs[0]+1 if n>1: f2 = min(f1+costs[1]+1,f0+costs[1]+4) for i in range(3,n+1): newf= min(f2+costs[i-1]+1,f1+costs[i-1]+4,f0+costs[i-1]+9) f0 = f1 f1 = f2 f2 = newf if n==1: return f1 if n>1: return f2

灵神版：

class Solution: def climbStairs(self, _, costs: List[int]) -> int: f0 = f1 = f2 = 0 for c in costs: f0, f1, f2 = f1, f2, min(f0 + 9, f1 + 4, f2 + 1) + c return f2 。

---

---

---

4.打家劫舍，房子首尾相连

就是在打家劫舍的基础上，多加一个判断nums[0]

如果取了nums[0]，做第三座房子到倒数第二座房子的打家劫舍

没取 ，做第二家房子到最后一家房子的打家劫舍

---

我的错误：因为在rob里面又嵌套了一个rob1，所以要注意参数，里面的就不是nums[ ]

class Solution: def rob(self, nums: List[int]) -> int: n = len(nums) def rob1(arr): f0=f1=0 for x in arr: newf = max(f1,f0+x) f0 = f1 f1 = newf return f1 return max(rob1(nums[2:n-1])+nums[0],rob1(nums[1:n]))

---

---

---

5.mxn棋盘最小路径和（左上走到右下）

回溯法：

1.dfs（i,j）定义：走到grid（i,j）一共走了多少路径

2.边界条件 if i<0 or j <0:

return 多少0？-1？

return inf设置一个 “无效的极大值”，让它在min()比较中被自动忽略

if i==0 and j==0：赋初值

3.怎么得到右下角的坐标，毕竟是mxn的，只知道一个数组

grid = [[1,3,1],[1,5,1],[4,2,1]]

要根据grid求出右下角的坐标

所以 横坐标是 len(grid)-1,纵坐标是len(grid[0])-1

class Solution: def minPathSum(self, grid: List[List[int]]) -> int: @cache def dfs(i,j): if i<0 or j <0: return inf if i == 0 and j == 0: return grid[0][0] return min(dfs(i,j-1),dfs(i-1,j))+grid[i][j] return dfs(len(grid)-1,len(grid[0])-1)

递推：

先根据dfs式子改成f式子

f[i + 1][j + 1] = min(f[i + 1][j], f[i][j + 1]) + grid[i][j]

初始值：f[0][j]=f[i][0]=∞，给整个grid左边上边加一排inf

f[1][1]=grid[0][0]

f[0][1]=f[1][0]=0 ，保证f[1][1] 也可以用递推式计算

---

难点1.怎么创建一个m*n的f[[][]],并且全部赋初值inf

m是len(grid) n是len（grid[0]）

f = [[inf] * (n + 1) for _ in range(m + 1)]

难点2.把每一行的列元素取出来

for i, row in enumerate(grid):
for j, x in enumerate(row):

时间复杂度mn 空间复杂度n

class Solution: def minPathSum(self, grid: List[List[int]]) -> int: m, n = len(grid), len(grid[0]) f = [[inf] * (n + 1) for _ in range(m + 1)] f[0][1] = 0 for i, row in enumerate(grid): for j, x in enumerate(row): f[i + 1][j + 1] = min(f[i + 1][j], f[i][j + 1]) + x return f[m][n]

空间优化：

可以优化到1，看不动了...