「动态规划 dynamic programming」是一个重要的算法范式，它将一个问题分解为一系列更小的子问题，并通过存储子问题的解来避免重复计算，从而大幅提升时间效率。在本节中，我们从一个经典例题入手，先给出它的暴力回溯解法，观察其中包含的重叠子问题，再逐步导出更高效的动态规划解法。
爬楼梯:给定一个共有𝑛 阶的楼梯，你每步可以上 1 阶或者 2 阶，请问有多少种方案可以爬到楼顶。
引子
回溯算法
class TrackBack: def __init__(self, target): self.target = target self.n = 0 self.choices = [1, 2] self.dfs(0) def dfs(self, state): if state == self.target: self.n += 1 for choice in self.choices: if state < self.target: state += choice self.dfs(state) state -= choice
暴力搜索
def dfs(target): if target == 1 or target == 2: return target return dfs(target-1) + dfs(target-2)
回溯和暴力搜索的缺点
时间复杂度为为 𝑂(2𝑛),递归地将一个较大问题拆解为两个较小问题的和,指数阶的时间复杂度是由于“重叠子问题”导致的
记忆搜索
为了提升算法效率,希望所有的重叠子问题都只被计算一次
记忆化搜索是一种“从顶至底”的方法:们从原问题（根节点）开始，递归地将较大子问题分解为较小子问题，直至解已知的最小子问题（叶节点）。
def dfs(target, mem): if target == 1 or target == 2: return target if mem[target] != 0: return mem[target] count = dfs(target-1, mem) + dfs(target-2, mem) mem[target] = count return count
动态规划
动态规划是一种“从底至顶”的方法:从最小子问题的解开始，迭代地构建更大子问题的解，直至得到原问题的解。动态规划不包含回溯过程，因此只需使用循环迭代实现，无须使用递归
def dfs(target): if target == 1 or target == 2: return target dp = [0,1,2] + [0] * (target) for i in range(3, target+1): dp[i] = dp[i-1] + dp[i-2] return dp[target]
动态规划
- 将数组 dp 称为「𝑑𝑝 表」，𝑑𝑝[𝑖] 表示状态𝑖 对应子问题的解。
- 将最小子问题对应的状态（即第1和2阶楼梯）称为「初始状态」。
- 将递推公式𝑑𝑝[𝑖] = 𝑑𝑝[𝑖 − 1] + 𝑑𝑝[𝑖 − 2]称为「状态转移方程」。
def dfs(target): if target == 1 or target == 2: return target a = 1 b = 2 for i in range(3, target+1): a, b = b, a + b return b
动态规划问题特性
子问题分解是一种通用的算法思路，在分治、动态规划、回溯中的侧重点不同。
- 分治算法递归地将原问题划分为多个相互独立的子问题，直至最小子问题，并在回溯中合并子问题的解，最终得到原问题的解。
- 动态规划也对问题进行递归分解，但与分治算法的主要区别是，动态规划中的子问题是相互依赖的，在分解过程中会出现许多重叠子问题。
- 回溯算法在尝试和回退中穷举所有可能的解，并通过剪枝避免不必要的搜索分支。原问题的解由一系列决策步骤构成，我们可以将每个决策步骤之前的子序列看作为一个子问题。
动态规划常用来求解最优化问题，它们不仅包含重叠子问题，还具有另外两大特性：最优子结构、无后效性。
最优子结构
爬楼梯最小代价:给定一个楼梯，你每步可以上 1 阶或者 2 阶，每一阶楼梯上都贴有一个非负整数，表示你在该台阶所需要付出的代价。给定一个非负整数数组 𝑐𝑜𝑠𝑡 ，其中 𝑐𝑜𝑠𝑡[𝑖] 表示在第 𝑖 个台阶需要付出的代价，𝑐𝑜𝑠𝑡[0] 为地面起始点。请计算最少需要付出多少代价才能到达顶部？
def dfs(cost): n = len(cost) - 1 dp = [0] * (n+1) a, b = cost[1], cost[2] for i in range(3, n+1): a, b = b, min(a, b) + cost[i] return b
无后效性
无后效性是动态规划能够有效解决问题的重要特性之一，定义为：给定一个确定的状态，它的未来发展只与当前状态有关，而与当前状态过去所经历过的所有状态无关。
带约束爬楼梯:给定一个共有𝑛 阶的楼梯，你每步可以上 1 阶或者 2 阶，但不能连续两轮跳 1 阶，请问有多少种方案可以爬到楼顶。
def dfs(target): dp = [[0]*3 for _ in range(target+1)] dp[1][1] = 1 dp[2][1] = 0 dp[2][2] = 1 for i in range(3, target+1): dp[i][1] = dp[i-1][2] dp[i][2] = dp[i-2][1] + dp[i-2][2] return dp[target][1] + dp[target][2]
判断是否为动态规划问题
总的来说，如果一个问题包含重叠子问题、最优子结构，并满足无后效性，那么它通常就适合用动态规划求解。然而，我们很难从问题描述上直接提取出这些特性。因此我们通常会放宽条件，先观察问题是否适合使用回溯（穷举）解决。
适合用回溯解决的问题通常满足“决策树模型”，这种问题可以使用树形结构来描述，其中每一个节点代表一个决策，每一条路径代表一个决策序列。
换句话说，如果问题包含明确的决策概念，并且解是通过一系列决策产生的，那么它就满足决策树模型，通常可以使用回溯来解决。
在此基础上，动态规划问题还有一些判断的“加分项”。
- 问题包含最大（小）或最多（少）等最优化描述。
- 问题的状态能够使用一个列表、多维矩阵或树来表示，并且一个状态与其周围的状态存在递推关系。
相应地，也存在一些“减分项”。
- 问题的目标是找出所有可能的解决方案，而不是找出最优解。
- 问题描述中有明显的排列组合的特征，需要返回具体的多个方案。
如果一个问题满足决策树模型，并具有较为明显的“加分项“，我们就可以假设它是一个动态规划问题，并在求解过程中验证它。
动态规划问题求解步骤
给定一个 𝑛 × 𝑚 的二维网格 grid ，网格中的每个单元格包含一个非负整数，表示该单元格的代价。机器人以左上角单元格为起始点，每次只能向下或者向右移动一步，直至到达右下角单元格。请返回从左上角到右下角的最小路径和。
第一步：思考每轮的决策，定义状态，从而得到 𝑑𝑝 表
本题的每一轮的决策就是从当前格子向下或向右一步。设当前格子的行列索引为[𝑖, 𝑗]，则向下或向右走一步后，索引变为[𝑖 + 1, 𝑗] 或 [𝑖, 𝑗 + 1] 。因此，状态应包含行索引和列索引两个变量，记为[𝑖, 𝑗] 。状态 [𝑖, 𝑗] 对应的子问题为：从起始点[0, 0]走到[𝑖, 𝑗] 的最小路径和，解记为𝑑𝑝[𝑖, 𝑗]。至此，我们就得到了图 14‑11 所示的二维𝑑𝑝矩阵，其尺寸与输入网格𝑔𝑟𝑖𝑑 相同。
动态规划和回溯过程可以被描述为一个决策序列，而状态由所有决策变量构成。它应当包含描述解题进度的所有变量，其包含了足够的信息，能够用来推导出下一个状态。每个状态都对应一个子问题，我们会定义一个 𝑑𝑝 表来存储所有子问题的解，状态的每个独立变量都是 𝑑𝑝 表的一个维度。本质上看，𝑑𝑝 表是状态和子问题的解之间的映射。
第二步：找出最优子结构，进而推导出状态转移方程
对于状态[𝑖, 𝑗] ，它只能从上边格子[𝑖 − 1, 𝑗] 和左边格子[𝑖, 𝑗 − 1] 转移而来。因此最优子结构为：到达[𝑖, 𝑗] 的最小路径和由[𝑖, 𝑗 − 1] 的最小路径和与[𝑖 − 1, 𝑗] 的最小路径和，这两者较小的那一个决定。根据以上分析，可推出图 14‑12 所示的状态转移方程：
根据定义好的 𝑑𝑝 表，思考原问题和子问题的关系，找出通过子问题的最优解来构造原问题的最优解的方法，即最优子结构。一旦我们找到了最优子结构，就可以使用它来构建出状态转移方程。
第三步：确定边界条件和状态转移顺序
在本题中，处在首行的状态只能向右转移，首列状态只能向下转移，因此首行 𝑖 = 0 和首列 𝑗 = 0 是边界条件。如图 14‑13 所示，由于每个格子是由其左方格子和上方格子转移而来，因此我们使用采用循环来遍历矩阵，外循环遍历各行、内循环遍历各列。
边界条件在动态规划中用于初始化 𝑑𝑝 表，在搜索中用于剪枝。状态转移顺序的核心是要保证在计算当前问题的解时，所有它依赖的更小子问题的解都已经被正确地计算出来。
根据以上分析，我们已经可以直接写出动态规划代码。然而子问题分解是一种从顶至底的思想，因此按照“暴力搜索 → 记忆化搜索 → 动态规划→ 空间优化”的顺序实现更加符合思维习惯。
暴力
def dfs(i, j, matric): if i == 0 and j == 0: return matric[0][0] if i < 0 or j < 0: return float('inf') left = dfs(i-1, j, matric) right = dfs(i, j-1, matric) return min(left, right) + matric[i][j]
记忆
def dfs(i, j, matric, map): if i == 0 and j == 0: return matric[0][0] if i < 0 or j < 0: return float('inf') if map[i][j] != -1: return map[i][j] left = dfs(i-1, j, matric, map) right = dfs(i, j-1, matric, map) map[i][j] = min(left, right) + matric[i][j] return map[i][j]
动态规划
def dfs(i, j, matric): n = len(matric) m = len(matric[0]) dp = [[0] * m for _ in range(n)] dp[0][0] = 1 for i in range(1, n): dp[i][0] = dp[i-1][0] + matric[i][0] for i in range(1, m): dp[0][i] = dp[0][i-1] + matric[0][i] for i in range(1, n): for j in range(1, m): dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + matric[i][j] return dp[n-1][m-1]
空间优化
def dfs(i, j, matric): n = len(matric) m = len(matric[0]) dp = [0] * n dp[0] = matric[0][0] for i in range(1,n): dp[i] = dp[i-1] + matric[i][0] for i in range(1,m): dp[0] = dp[0] + matric[0][i] for j in range(1,n): dp[j] = min(dp[j-1], dp[j]) + matric[j][i] return dp[-1]
0-1背包问题
暴力
def dfs(wgt, val, i, c): if i == 0 or c == 0: return 0 if wgt[i-1] > c: return dfs(wgt, val, i-1, c) else: no = dfs(wgt, val, i-1, c) yes = dfs(wgt, val, i-1, c-wgt[i-1]) + val[i-1] return max(yes, no)
记忆
def dfs(wgt, val, i, c, mem): if i == 0 or c == 0: return 0 if wgt[i-1] > c: return dfs(wgt, val, i-1, c, mem) if mem[i][c] != -1: return mem[i][c] yes = dfs(wgt, val, i-1, c-wgt[i-1], mem) + val[i-1] no = dfs(wgt, val, i-1, c, mem) mem[i][c] = max(yes, no) return mem[i][c]
动态规划
def dfs(wgt, val, i, c): dp = [[0]*(c+1) for _ in range(i+1)] for ix in range(1, i+1): for jx in range(1, c+1): if jx < wgt[ix-1]: dp[ix][jx] = dp[ix-1][jx] else: dp[ix][jx] = max(dp[ix-1][jx-wgt[ix-1]] + val[ix-1], dp[ix-1][jx]) return dp[i][c]
空间优化
def dfs(wgt, val, i, c): dp = [0] * (c+1) for ix in range(1, i+1): for jx in range(c, 0, -1): if jx < wgt[ix-1]: dp[jx] = dp[jx-1] else: dp[jx] = max(dp[jx], dp[jx-wgt[ix-1]] + val[ix-1]) return dp[c]
完全背包问题
暴力
def dfs(wgt, val, i, c): if i == 0 or c == 0: return 0 if wgt[i-1] > c: return dfs(wgt, val, i-1, c) else: no = dfs(wgt, val, i-1, c) yes = dfs(wgt, val, i, c-wgt[i-1]) + val[i-1] return max(yes, no)
记忆
def dfs(wgt, val, i, c, mem): if i == 0 or c == 0: return 0 if wgt[i-1] > c: return dfs(wgt, val, i-1, c, mem) if mem[i][c] != -1: return mem[i][c] yes = dfs(wgt, val, i, c-wgt[i-1], mem) + val[i-1] no = dfs(wgt, val, i-1, c, mem) mem[i][c] = max(yes, no) return mem[i][c]
动态规划
def dfs(wgt, val, i, c): dp = [[0]*(c+1) for _ in range(i+1)] for ix in range(1, i+1): for jx in range(0, c+1): if jx < wgt[ix-1]: dp[ix][jx] = dp[ix-1][jx] else: dp[ix][jx] = max(dp[ix][jx-wgt[ix-1]] + val[ix-1], dp[ix-1][jx]) return dp[i][c]
空间优化
def dfs(wgt, val, i, c): dp = [0] * (c+1) for ix in range(1, i+1): for jx in range(1, c+1): if jx < wgt[ix-1]: dp[jx] = dp[jx] else: dp[jx] = max(dp[jx], dp[jx-wgt[ix-1]] + val[ix-1]) return dp[c]
零钱兑换问题I
给定 𝑛 种硬币，第 𝑖 种硬币的面值为 𝑐𝑜𝑖𝑛𝑠[𝑖 − 1] ，目标金额为 𝑎𝑚𝑡 ，每种硬币可以重复选取，问能够凑出目标金额的最少硬币个数。如果无法凑出目标金额则返回−1 。
暴力（不行）
def dfs(weights, target, count): if target == 0: return count if target < 0 : return -1 lst = [] for weight in weights: summ = dfs(weights, target-weight, count + 1) if summ > 0: lst.append(summ) if lst: return min(lst) else: return -1
回溯（不行）
def dfs(weights, target, state, res): if target == 0: res.append(len(state)) for weight in weights: if target > 0: state.append(weight) dfs(weights, target-weight, state, res) state.pop() weights = [1,2,5] target = 20 state = [] res = [] dfs(weights, target, state, res) min(res)
记忆(可以)
def dfs_help(weights, target, mem): if target == 0: return 0 if mem[target] != -1: return mem[target] lst = [] for weight in weights: if target >= weight: summ = dfs_help(weights, target - weight, mem) if summ >= 0: lst.append(summ + 1) if lst: return min(lst) return -1 def dfs(weights, target): mem = [-1] * (target + 1) for i in range(target + 1): mem[i] = dfs_help(weights, i, mem) return mem[-1]
动态规划
def dfs(weights, target): n, m = len(weights), target dp = [[0]*(m+1) for _ in range(n+1)] for i in range(1, target+1): dp[0][i] = float('inf') for i in range(1, n+1): for j in range(0, m+1): if j < weights[i-1]: dp[i][j] = dp[i-1][j] else: dp[i][j] = min(dp[i][j-weights[i-1]], dp[i-1][j]) + 1 return dp
空间优化
def dfs(weights, target): n, m = len(weights), target dp = [0] * (target + 1) for i in range(1, target+1): dp[i] = float('inf') for i in range(1, n+1): for j in range(0, m+1): if j < weights[i-1]: dp[j] = dp[j] else: dp[j] = min(dp[j-weights[i-1]], dp[j]) + 1 return dp[m]
零钱兑换问题II
动态规划
def dfs(weights, target): n, m = len(weights), target dp = [[0] * (m+1) for _ in range(n+1)] for i in range(0, n+1): dp[i][0] = 1 for i in range(1, n+1): for j in range(1, m+1): if j < weights[i-1]: dp[i][j] = dp[i-1][j] else: dp[i][j] = dp[i][j - weights[i-1]] + dp[i-1][j] return dp[n][m]
空间优化
def dfs(weights, target): n, m = len(weights), target dp = [0] * (m+1) dp[0] = 1 for i in range(1, n+1): for j in range(1, m+1): if j < weights[i-1]: dp[j] = dp[j] else: dp[j] = dp[j - weights[i-1]] + dp[j] return dp[m]
字符串相似度问题
动态规划
def dfs(str_1, str_2): n, m = len(str_1), len(str_2) dp = [[0]*(m+1) for _ in range(n+1)] for i in range(1+m): dp[0][i] = i for i in range(1+n): dp[i][0] = i for i in range(1, n+1): for j in range(1, m+1): if str_1[i-1] == str_2[j-1]: dp[i][j] = dp[i-1][j-1] else: dp[i][j] = min(dp[i-1][j], dp[i-1][j-1], dp[i][j-1]) + 1 return dp[n][m] dfs('bag', 'pack')
空间优化
def dfs(str_1, str_2): n, m = len(str_1), len(str_2) dp = [0]*(m+1) for i in range(m+1): dp[i] = i for i in range(1, n+1): leftup = dp[0] dp[0] = i for j in range(1, m+1): tmp = dp[j] if str_1[i-1] == str_2[j-1]: dp[j] = dp[j-1] else: dp[j] = min(dp[j], leftup, dp[j-1]) + 1 leftup, tmp = tmp, leftup return dp[m] dfs('bag', 'pack')
重点回顾
- 动态规划对问题进行分解，并通过存储子问题的解来规避重复计算，实现高效的计算效率。
- 不考虑时间的前提下，所有动态规划问题都可以用回溯（暴力搜索）进行求解，但递归树中存在大量的重叠子问题，效率极低。通过引入记忆化列表，可以存储所有计算过的子问题的解，从而保证重叠子问题只被计算一次。
- 记忆化递归是一种从顶至底的递归式解法，而与之对应的动态规划是一种从底至顶的递推式解法，其如同“填写表格”一样。由于当前状态仅依赖于某些局部状态，因此我们可以消除 𝑑𝑝 表的一个维度，从而降低空间复杂度。
- 子问题分解是一种通用的算法思路，在分治、动态规划、回溯中具有不同的性质。
- 动态规划问题的三大特性：重叠子问题、最优子结构、无后效性。
- 如果原问题的最优解可以从子问题的最优解构建得来，则它就具有最优子结构。
- 无后效性指对于一个状态，其未来发展只与该状态有关，与其所经历的过去的所有状态无关。许多组合优化问题都不具有无后效性，无法使用动态规划快速求解。
背包问题 - 背包问题是最典型的动态规划题目，具有 0‑1 背包、完全背包、多重背包等变种问题。
- 0‑1 背包的状态定义为前𝑖 个物品在剩余容量为 𝑐 的背包中的最大价值。根据不放入背包和放入背包两种决策，可得到最优子结构，并构建出状态转移方程。在空间优化中，由于每个状态依赖正上方和左上方的状态，因此需要倒序遍历列表，避免左上方状态被覆盖。
- 完全背包的每种物品的选取数量无限制，因此选择放入物品的状态转移与 0‑1 背包不同。由于状态依赖于正上方和正左方的状态，因此在空间优化中应当正序遍历。
- 零钱兑换问题是完全背包的一个变种。它从求“最大”价值变为求“最小”硬币数量，因此状态转移方程中的 max() 应改为 min() 。从求“不超过”背包容量到求“恰好”凑出目标金额，因此使用 𝑎𝑚𝑡 + 1来表示“无法凑出目标金额”的无效解。
- 零钱兑换 II 问题从求“最少硬币数量”改为求“硬币组合数量”，状态转移方程相应地从 min() 改为求和运算符。
编辑距离问题 - 编辑距离（Levenshtein 距离）用于衡量两个字符串之间的相似度，其定义为从一个字符串到另一个字符串的最小编辑步数，编辑操作包括添加、删除、替换。
- 编辑距离问题的状态定义为将𝑠的前 𝑖 个字符更改为𝑡 的前 𝑗 个字符所需的最少编辑步数。当𝑠[𝑖] ≠ 𝑡[𝑗]时，具有三种决策：添加、删除、替换，它们都有相应的剩余子问题。据此便可以找出最优子结构与构建状态转移方程。而当𝑠[𝑖] = 𝑡[𝑗]时，无须编辑当前字符。
- 在编辑距离中，状态依赖于其正上方、正左方、左上方的状态，因此空间优化后正序或倒序遍历都无法正确地进行状态转移。为此，我们利用一个变量暂存左上方状态，从而转化到与完全背包等价的情况，可以在空间优化后进行正序遍历。
