动态规划
讨论框架
# 自顶向下递归的动态规划
def dp(状态1, 状态2, ...):
for 选择 in 所有可能的选择:
# 此时的状态已经因为做了选择而改变
result = 求最值(result, dp(状态1, 状态2, ...))
return result
# 自底向上迭代的动态规划
# 初始化 base case
dp[0][0][...] = base case
# 进行状态转移
for 状态1 in 状态1的所有取值：
for 状态2 in 状态2的所有取值：
for ...
dp[状态1][状态2][...] = 求最值(选择1，选择2...)
解题步骤
1.确定dp状态，即dp[]含义
2.确定状态转移方程
3.确定初始化状态
4.确定状态转移顺序
5.确定最优解
从刷题理解开始
斐波那契数列
斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：
F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1
给定 n ，请计算 F(n) 。
0 1 1 2 3 5 8 13 21 34 55
class Solution:
def fib(self, n: int) -> int:
if n < 2:
return n
dp=[0]*(n+1)
dp[0]=0
dp[1]=1
for i in range(2,n+1):
dp[i]=dp[i-1]+dp[i-2]
return dp[n]
爬楼梯
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
示例 ：
输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶
class Solution:
def climbStairs(self, n: int) -> int:
# dp[i] 为第 i 阶楼梯有多少种方法爬到楼顶
dp=[0]*(n+1) #生成一个列表，n+1个，与下面循环一直
dp[0]=1
dp[1]=1
for i in range(2,n+1):
dp[i]=dp[i-1]+dp[i-2]
return dp[n]
class Solution:
def climbStairs(self, n: int) -> int:
if n <= 1:
return n
# n 的取值范围 [1, 45]，这里将 dp[0] = 0
dp = [0] * (n + 1)
dp[1] = 1
dp[2] = 2
for i in range(3, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
易错点
dp是n+1个
最小花费爬楼梯
给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。
你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
请你计算并返回达到楼梯顶部的最低花费。
示例 ：
输入：cost = [10,15,20]
输出：15
解释：你将从下标为 1 的台阶开始。
- 支付 15 ，向上爬两个台阶，到达楼梯顶部。
总花费为 15 。
____
│ o │
__20____|___|
__15__│
__10__│
__起点__│
class Solution:
def climb(cost):
n=len(cost)
dp=[0]*(n+1)
dp[0]=0
dp[1]=0
for i in range(2,n+1):
dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2])
return dp[n]
易错点
n需要自己计算获得
不同路径
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？
- 输入：m = 3, n = 7
- 输出：28
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
# 初始化 dp 数组，m 行 n 列
dp = [[0] * n for _ in range(m)]
#这样写有一个坏处就是，m=n=1时 最后结果跑出来会是0，根据实际意义应该是1
#有两种方案解决这个问题：①dp = [[1] * n for _ in range(m)] 默认设为1
# ②初始化之前加：if m==n==1:return 1
# 初始化第 1 列
for i in range(1, m):
dp[i][0] = 1
# 初始化第 1 行
for i in range(1, n):
dp[0][i] = 1
# 状态转移方程
for i in range(1, m):
for j in range(1, n):
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
return dp[m - 1][n - 1]
a=Solution()
print(a.uniquePaths(1, 1))
易错点
原点的处理
不同路径2
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish”）。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
网格中的障碍物和空位置分别用 1 和 0 来表示。
输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输出：2
解释：3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右
class Solution:
def uniquePathsWithObstacles(self, obstacleGrid) -> int:
row = len(obstacleGrid)
col = len(obstacleGrid[0])
dp = [[0] * col for _ in range(row)]
# 如果在起点或者终点有障碍物，返回 0
if obstacleGrid[0][0] == 1 or obstacleGrid[row - 1][col - 1] == 1:
return 0
# 初始化行和列
for i in range(col): # 这里的指的是列，对行初始化，列在遍历
if obstacleGrid[0][i] == 0:
dp[0][i] = 1
else:
break
for j in range(row):
if obstacleGrid[j][0] == 0:
dp[j][0] = 1
else:
break
for i in range(1, row): # i代表的是行，取值是row
for j in range(1, col):
if obstacleGrid[i][j] == 0:
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
return dp[row - 1][col - 1]
#或dp[-1][-1]
易错点
和最小路径和不同，初始化行列时，要从0开始，即for i in range(col)，不是for i in range(1，col)
最小路径和
给定一个包含非负整数的 *m* x *n* 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
示例 ：
输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。
class Solution:
def minPathSum(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
dp = [[0] * n for _ in range(m)]
#初始化起点,对于起点 (0,0) 来说，它的最小路径和就是 (0,0) 网格本身的值
dp[0][0]=grid[0][0]
# 初始化第一行
for i in range(1,n):
dp[0][i] = dp[0][i - 1] + grid[0][i]
for i in range(1,m):
dp[i][0] = dp[i - 1][0] + grid[i][0]
for i in range(1,m):
for j in range(1,n):
dp[i][j] = min(dp[i - 1][j] , dp[i][j-1])+ grid[i][j]
return dp[-1][-1]
易错点
dp = [[0] * col for _ in range(row)] 不要忘记0的中括号
初始化第一行、第一列索引是0
初始化起点
状态转移方程：不应该是dp[i][j] = min(dp[i - 1][j] + grid[i][j], dp[i][j-1]+ grid[i][j])
应该是dp[i][j] = min(dp[i - 1][j] , dp[i][j-1])+ grid[i][j]注意和最小花费爬楼梯的区别
所有的范围必须是从1开始,即range(1,m),千万注意range(m)从0开始取因为有dp[0][i-1]z这一项
只有左边界，意味着该矩阵只有一列；只有上边界，意味着该矩阵只有一行；左边和上边都是边界，意味着该矩阵只有一个元素。
解法二
class Solution:
def minPathSum(self, grid: [[int]]) -> int:
for i in range(len(grid)):
for j in range(len(grid[0])):
if i == j == 0: continue
elif i == 0: grid[i][j] = grid[i][j - 1] + grid[i][j]
elif j == 0: grid[i][j] = grid[i - 1][j] + grid[i][j]
else: grid[i][j] = min(grid[i - 1][j], grid[i][j - 1]) + grid[i][j]
return grid[-1][-1]
整数拆分
给定一个正整数 n ，将其拆分为 k 个 正整数 的和（ k >= 2 ），并使这些整数的乘积最大化。
返回 你可以获得的最大乘积 。
class Solution:
def integerBreak(self, n: int) -> int:
dp=[0]*(n+1)
dp[2]=1
for i in range(3,n+1):
for j in range(1,i):
# 对于正整数 i，拆分的第一个正整数是 j(1 ≤ j ≤ i - 1)，存在两种情况：
# 第 1 种：i 拆分成 j 和 i - j，且 i - j 不可再拆分，此时乘积为 i * (i - j)
# 第 2 种：i 拆分成 j 和 i - j，且 i - j 可拆分，此时乘积是 i * dp[i- j]
dp[i]=max(dp[i],j*dp[i-j],j*(i-j))
return dp[n]
易错点
递归方程中，取大时，需要加入当前最大值dp[i]
比如在计算6✖️2 时，我不仅要比较j*dp[i-j],j*(i-j),我还要比较上面7✖️1的最优结果dp[i]