# 动态规划 动态规划把问题拆成子问题，保存每个子问题的答案，再按依赖顺序复用，避免同一状态被反复计算。它适用于子问题大量重叠、且原问题最优解由子问题最优解构成的问题。本页用最长递增子序列和0/1背包说明状态、转移、边界和方案还原的写法。子问题互不重叠时，分解方式见[分治法](/knowledge/cs/algorithms/divide-and-conquer/)；记忆化仍然借助[递归](/knowledge/cs/algorithms/recursion/)的调用与返回。 ## 定义 **动态规划**把原问题拆成若干子问题，为每个子问题定义状态并保存其答案，再按依赖顺序用子问题的答案计算当前状态。 一个动态规划方案包含四部分： * **状态**：用一个或一组变量描述子问题，例如`a[i][j]` 表示“前`i`件物品、容量为`j`时的最大价值”。 * **转移**：当前状态由哪些更小状态、按什么规则得到。 * **边界**：最小子问题的答案，例如没有物品或容量为0时价值为0。 * **计算顺序**：保证计算当前状态时，它依赖的状态已经算好。 同样的状态和转移可以用两种方式实现：自底向上按顺序填表，或自顶向下递归并缓存结果（记忆化）。 ## 性质 ### 适用条件 * **重叠子问题**：不同的计算路径会反复遇到同一个子问题。若子问题互不重叠，分治就够了，保存答案不会减少工作量。 * **最优子结构**：原问题的最优解可以由子问题的最优解组合得到。 * **无后效性**：状态一旦确定，后续计算只依赖这个状态，不依赖到达它的具体路径。状态设计必须把影响后续选择的信息都包含进去。 > [!IMPORTANT] > 状态定义决定了转移是否正确。若两个本质不同的局面被压成同一个状态，转移会把它们混在一起；若状态包含无关信息，状态数会不必要地膨胀。 ### 自底向上与记忆化 | 写法 | 计算方式 | 优点 | 代价 | | ---- | ------------- | ------------------ | -------------------- | | 自底向上 | 按依赖顺序填表 | 无递归调用开销，便于控制空间 | 必须先确定计算顺序，可能计算用不到的状态 | | 记忆化 | 递归求解，查表命中直接返回 | 只计算真正需要的状态，形式贴近递推式 | 有调用栈深度限制，函数调用有额外开销 | 两种写法使用同一组状态和转移，时间复杂度通常相同，差别在常数、空间和实现难度。 ### 与分治、贪心的对比 动态规划与分治都拆子问题，区别是动态规划保存并复用子问题的答案；与贪心的区别是动态规划会比较多个候选，不提前固定一个选择。判断顺序可以是：子问题重叠就考虑动态规划；能证明局部最优可扩展到全局最优就用贪心；子问题独立且合并代价可控就用分治。 ### 设计步骤 1. **定义状态** 用一个明确的量回答“子问题是什么”，写清下标的含义和取值范围。 2. **写出转移** 枚举当前状态的最后一步，把它化成一个或几个更小状态，并说明取最大、最小还是求和。 3. **确定边界** 写出最小规模下的答案，检查转移在边界处不会越界。 4. **确定顺序** 让转移依赖的状态先被计算；自底向上时通常按下标从小到大填表。 5. **还原方案** 若题目要求具体方案而不只是最优值，另开一个数组记录每个状态的选择，最后从终点回溯。 ### 代价 状态数为 $N$、每个状态转移检查 $K$ 个候选时，时间为 $O(NK)$，空间为 $O(N)$（或按需压缩）。背包的二维表有 $(n+1)(m+1)$ 个状态；最长递增子序列的`Asc`有 $n$ 个状态，每个状态扫描它前面的所有元素，因此是 $O(n^2)$。 ## 例子 **最长递增子序列：按结尾元素定义状态** 最长递增子序列要求从列表中按原顺序取出一个子序列，使数值严格递增，并让长度最大。子序列不要求元素在列表中相邻。 ```python title="lis-dp.py" def LIS(L): Asc = [1] * len(L) Tra = [-1] * len(L) # Asc[i] 存放以L[i]结尾的最长递增子序列长度。 # Tra[i] 存这个子序列中L[i]的前一个元素下标，用于还原序列。 for i in range(1, len(L)): X = [] for j in range(0, i): if L[i] > L[j]: X.append(j) for k in X: if Asc[i] < Asc[k] + 1: Asc[i] = Asc[k] + 1 Tra[i] = k print("Asc:", Asc) print("Tra:", Tra) best = 0 for i in range(1, len(Asc)): if Asc[i] > Asc[best]: best = i print("最长递增子序列的长度是", Asc[best]) X = [L[best]] i = best while Tra[i] >= 0: X = [L[Tra[i]]] + X i = Tra[i] print("最长递增子数列=", X) L = [5, 2, 4, 7, 6, 3, 8, 9] LIS(L) ``` 状态`Asc[i]` 表示“以`L[i]` 结尾”的最长递增子序列长度，边界是每个元素单独构成子序列时的长度1。转移检查所有`j < i`且`L[j] < L[i]` 的前驱，取`Asc[j] + 1`的最大值。`Tra[i]` 记录取得最大值的那个`j`，最后从最长长度所在的下标向前回溯，就能得到具体序列。 对`L = [5, 2, 4, 7, 6, 3, 8, 9]`，程序输出`Asc`为 `[1, 1, 2, 3, 3, 2, 4, 5]`，最大长度为5；按`Tra`回溯得到 `[2, 4, 7, 8, 9]`。长度为5的递增子序列不唯一，`[2, 4, 6, 8, 9]` 同样合法，但`Tra`在长度相同的候选中保留了先遇到的下标，所以这段代码还原的是前者。 > [!NOTE] > 当`Asc[i]` 与`Asc[k] + 1`相等时，代码不更新`Tra[i]`。因此`Tra`只保证能还原出一条最长序列，不保证它是字典序最小或元素和最大的那一条。 **同一问题的直接递归写法** 不保存答案，直接按定义展开，也能写出同一个状态： ```python title="lis-recursive.py" def Asc(k): if k == 0: return 1 X = [] for i in range(0, k): if L[k] > L[i]: X.append(Asc(i)) if len(X) > 0: return max(X) + 1 else: return 1 def LIS_R(L): X = [] for k in range(0, len(L)): X.append(Asc(k)) print(X) print(max(X)) L = [5, 2, 4, 7, 6, 3, 8, 9] LIS_R(L) ``` `Asc(k)` 的含义与动态规划版完全相同，但每次调用都重新展开所有更小的下标。以递增列表为例，`Asc(k)` 会调用`Asc(0)` 到`Asc(k-1)`，调用次数满足 $T(k)=1+\sum_{i= w[n]) and (knap_r(n - 1, j - w[n]) + v[n] > knap_r(n - 1, j)): x[n] = True return knap_r(n - 1, j - w[n]) + v[n] else: x[n] = False return knap_r(n - 1, j) print("最大价值为：", knap_r(n, j)) print("物品的装入情况为：", x[1:]) ``` `knap_r(n, j)` 表示“只考虑前`n`件物品、容量为`j`时的最大价值”。若第`n`件能放下，就比较“放入它”和“不放入它”两种结果，取较大者；否则只能不放。 问题在于，比较两个分支时每一支都会再次递归，`knap_r(n-1, j-w[n])` 和`knap_r(n-1, j)` 内部又共享大量更小的子问题。同一个 `(n, j)` 被重复求解，调用次数随物品数指数增长。 **0/1背包：自底向上填表** 把“前`i`件物品、容量`j`”的全部组合列成二维表，按`i`从小到大、`j`从小到大填写，每个状态只算一次。 ```python title="knapsack-dp.py" w = [0, 4, 5, 2, 1, 6] v = [0, 45, 57, 22, 11, 67] n = len(w) - 1 m = 8 x = [False for raw in range(n + 1)] a = [[0 for col in range(m + 1)] for raw in range(n + 1)] def knap_DP(n, m): for i in range(1, n + 1): for j in range(1, m + 1): a[i][j] = a[i - 1][j] if (j >= w[i]) and (a[i - 1][j - w[i]] + v[i] > a[i - 1][j]): a[i][j] = a[i - 1][j - w[i]] + v[i] j = m for i in range(n, 0, -1): if a[i][j] > a[i - 1][j]: x[i] = True j = j - w[i] return a[n][m] print("最大价值为：", knap_DP(n, m)) print("物品的装入情况为：", x[1:]) ``` `a[i][j]` 的转移分两种情形：容量`j`放不下第`i`件物品时，价值只能继承`a[i-1][j]`；放得下时，在“不放”与“放”之间取较大值： $$ a[i][j]=\max\bigl(a[i-1][j],\ a[i-1][j-w[i]]+v[i]\bigr),\qquad j\ge w[i]. $$ 边界是`a[0][j] = 0`和`a[i][0] = 0`。填表完成后，从`a[n][m]` 向前回溯：若`a[i][j] > a[i-1][j]`，说明第`i`件物品被放入，把`j`减去它的重量；否则这件物品没有放入。 对给定的重量、价值和容量8，最大价值为90，装入的是第2、3、4件物品，重量 $5+2+1=8$。时间复杂度为 $O(nm)$，空间为 $O(nm)$。 > [!TIP] > 二维表可以压成一维数组，只保留当前容量对应的值。此时`j`必须从大到小更新，否则同一件物品会在同一次填表中被重复使用，0/1背包就变成了完全背包。 ## 交互探索 查看找零问题中每个金额的最优结果，比较当前状态与它的前驱状态。 交互演示：较小金额的结果怎样组成最优解？。查看不同金额所需的最少硬币数及其状态转移。 请在站点操作演示。 ## 练习 1. 对`L = [5, 2, 4, 7, 6, 3, 8, 9]`，按动态规划版`LIS(L)` 计算，最长递增子序列的长度是 \_\_\_\_\_\_（length）。 答案：5 `Asc`为 `[1, 1, 2, 3, 3, 2, 4, 5]`，最大值为5。 2. 同一段代码按`Tra`回溯，输出的最长递增子序列是： * A. `[2, 4, 7, 8, 9]` * B. `[5, 7, 8, 9]` * C. `[2, 4, 6, 8]` * D. `[2, 3, 6, 8, 9]` 答案：A 从下标7的9开始，`Tra[7]=6`取8，`Tra[6]=3`取7，`Tra[3]=2`取4，`Tra[2]=1`取2，得到 `[2, 4, 7, 8, 9]`。 3. 对`w = [0, 4, 5, 2, 1, 6]`、`v = [0, 45, 57, 22, 11, 67]`、容量8，0/1背包的最大价值是 \_\_\_\_\_\_（value）。 答案：90 取第2、3、4件物品，重量 $5+2+1=8$，价值 $57+22+11=90$。 4. 背包的递归写法`knap_r(n, j)` 在物品数增大时变慢，主要原因是： * A. 同一个 `(n, j)` 状态被不同分支重复求解，没有保存结果 * B. 递归无法处理容量为0的情况 * C. 递归只能处理重量递增的物品 * D. 递归写法要求物品按重量从小到大排列 答案：A 两个分支各自递归，内部又共享大量更小的子问题；保存每个 `(n, j)` 的答案、让每个状态只算一次，就得到动态规划版。 5. 下列哪一项不是动态规划的必要条件？ * A. 最优子结构 * B. 重叠子问题 * C. 无后效性 * D. 子问题相互独立，彼此不会重复 答案：D 动态规划恰恰利用子问题的重叠来复用答案。子问题相互独立是分治的典型条件，不是动态规划的必要条件。 6. 记忆化指的是： * A. 保留递归形式，把已经算过的状态存起来，再次遇到时直接返回 * B. 把所有状态按顺序填进表格，完全不用递归 * C. 在递归函数中打印每次调用的参数 * D. 把二维表压缩成一维数组 答案：A 记忆化是自顶向下的实现方式：仍然递归，但用表缓存结果。按顺序填表、不用递归是自底向上的写法。