· 算法设计与分析 / 动态规划 / 最长公共子序列 / 0-1背包 / 最长递增子序列
算法设计与分析 Day7:动态规划进阶
RedMoon · 2026-11-05 · 课堂阅读笔记

本次课围绕动态规划的状态设计与转移展开:从网格路径计数进入二维状态,再用最长公共子序列(LCS)和 0-1 背包说明如何处理序列匹配与受容量约束的选择问题。课后作业继续沿着这条主线,分别把矩阵链乘法的目标改为最大化,并设计 $O(n^2)$ 与 $O(n\log n)$ 的最长递增子序列算法。
动态规划的关键不是套用某条公式,而是准确说明每个状态回答什么问题、当前答案依赖哪些更小状态,以及如何按依赖顺序计算。若还要输出具体方案,就需要保存足够的决策或前驱信息。
一、动态规划的设计顺序
分治和动态规划都将原问题拆成子问题再组合。典型动态规划中,同一子问题会被多次用到,因此把已经求出的状态保存下来,可以避免重复计算。状态设计要保留组合答案所需的信息;只要遗漏了影响后续选择的条件,转移式即使形式正确,也可能无法表达原问题。
设计时依次回答以下问题:
- 状态是什么:明确状态所代表的子问题,例如“前 $i$ 个元素的答案”或“区间 $[i,j]$ 的答案”。
- 如何转移:观察最后一步或当前元素的选择,把所有可能情况写全。
- 边界是什么:给出最小子问题的答案,避免转移引用未定义状态。
- 按什么顺序计算:确保每个状态依赖的子状态已经有值。
- 怎样恢复方案:若只求最优值,状态表通常够用;若要输出具体解,还需记录选择或前驱。
- 复杂度是多少:统计状态数量,并乘以每个状态枚举的转移数;再检查能否滚动保存状态。
证明递推正确时,可以说明两件事:每个可行解都对应转移中枚举的一种情况;转移采用的子状态确实能组成该情况下的最优解。这样既解释了“没有漏解”,也解释了“不会得到不可行或非最优的结果”。
二、机器人网格路径计数
设网格有 $M$ 行、$N$ 列,机器人从左上角出发,只能向右或向下移动,求到达右下角的路径数。这里没有障碍格。
令 $P[i][j]$ 表示从左上角到第 $i$ 行、第 $j$ 列的路径数。第一行只能一直向右,第一列只能一直向下,因此:
\[P[1][j]=1,\qquad P[i][1]=1.\]其他格子只能从上方或左方进入:
\[P[i][j]=P[i-1][j]+P[i][j-1].\]按行、按列从小到大填表即可,因为上方和左方状态都已计算。共有 $MN$ 个状态,每个状态只做常数次运算,时间复杂度为 $O(MN)$。若只需要路径总数,可以把较短的一维作为滚动数组,空间降为 $O(\min(M,N))$;若需要逐格查看结果,则保留完整表格。
这个例子体现了状态设计的起点:先观察到达当前格的最后一步可能来自哪里,再把这些互斥来源的路径数相加。
三、最长公共子序列
1. 子序列与子数组
子序列保留原有相对顺序,但允许跳过元素;子数组则要求元素连续。因此,子数组是子序列的一种特殊情况。LCS(Longest Common Subsequence)给定序列 $X$ 和 $Y$,要求找出同时是两者子序列、且长度最大的序列。
课件用“相同元素之间连线且连线不交叉”作直观解释:不交叉保证所选元素在两个原序列中的相对顺序一致。
2. 状态与递推
令 $C[i][j]$ 表示 $X$ 的前 $i$ 个元素与 $Y$ 的前 $j$ 个元素的 LCS 长度。空前缀没有非空公共子序列:
\[C[0][j]=0,\qquad C[i][0]=0.\]观察两个前缀的末尾元素:
- 若 $X_i=Y_j$,这两个相同元素可以匹配,长度在两个更短前缀的答案上增加 1。
- 若 $X_i\ne Y_j$,两者不可能同时作为同一条公共子序列的末尾,至少要舍弃一个末尾元素,分别比较两个方向。
于是:
\[C[i][j]= \begin{cases} C[i-1][j-1]+1, & X_i=Y_j,\\ \max(C[i-1][j],C[i][j-1]), & X_i\ne Y_j. \end{cases}\]按 $i=1,\ldots,m$、$j=1,\ldots,n$ 逐行填表,当前状态依赖上方、左方和左上方。表格有 $mn$ 个非边界状态,每个状态只检查常数个候选,所以求长度的时间为 $O(mn)$,完整表格的空间为 $O(mn)$。
从表格右下角回溯可恢复一个 LCS:若 $X_i=Y_j$,记录该元素并向左上移动;否则沿着数值较大的上方或左方移动。若两侧相等,任取一侧都能得到一个最长解,但具体序列可能不同。若只求长度,可以用两行滚动数组,把空间降至 $O(\min(m,n))$;若还要恢复序列,则需要保留回溯信息,或采用线性空间的专门算法。
四、0-1 背包
1. 状态和选择
有 $n$ 个物品,第 $i$ 个物品的重量为 $w_i$、价值为 $v_i$;背包容量为 $W$。每件物品只能整件取或不取,求不超过容量时的最大总价值。
令 $S[i][k]$ 表示只考虑前 $i$ 件物品、背包容量为 $k$ 时能够取得的最大价值。边界为:
\[S[0][k]=0,\qquad S[i][0]=0.\]处理第 $i$ 件物品时:
- 若 $w_i>k$,装不下,只能沿用 $S[i-1][k]$。
- 若 $w_i\le k$,比较不装与装入两种情况。装入后,剩余容量为 $k-w_i$,且只能从前 $i-1$ 件物品中继续选择。
因此:
\[S[i][k]= \begin{cases} S[i-1][k], & w_i>k,\\ \max\left(S[i-1][k],v_i+S[i-1][k-w_i]\right), & w_i\le k. \end{cases}\]这个定义中的“前 $i$ 件物品”很重要:选入第 $i$ 件后,子问题仍只用前 $i-1$ 件,保证同一件物品不会重复使用。
2. 课件算例
容量 $W=5$,物品按顺序为:
| 物品 $i$ | 重量 $w_i$ | 价值 $v_i$ |
|---|---|---|
| 1 | 3 | 2.5 |
| 2 | 1 | 1.9 |
| 3 | 2 | 3 |
| 4 | 1 | 1 |
| 5 | 4 | 3 |
下表列出每个物品前缀、各容量下的最优价值:
| 已考虑物品 | $k=0$ | $k=1$ | $k=2$ | $k=3$ | $k=4$ | $k=5$ |
|---|---|---|---|---|---|---|
| 无 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 2.5 | 2.5 | 2.5 |
| 1–2 | 0 | 1.9 | 1.9 | 2.5 | 4.4 | 4.4 |
| 1–3 | 0 | 1.9 | 3 | 4.9 | 4.9 | 5.5 |
| 1–4 | 0 | 1.9 | 3 | 4.9 | 5.9 | 5.9 |
| 1–5 | 0 | 1.9 | 3 | 4.9 | 5.9 | 5.9 |
最终 $S[5][5]=5.9$。回溯时,第 5 件不选,因为 $S[5][5]=S[4][5]$;第 4 件选入后容量变成 4;第 3 件选入后容量变成 2;第 2 件选入后容量变成 1;第 1 件不选。因此一个最优方案是选择物品 2、3、4,总重量为 $1+2+1=4$,总价值为 $1.9+3+1=5.9$。
状态数为 $nW$,每个状态的转移为常数时间,因此时间复杂度为 $O(nW)$。由于 $W$ 是容量的数值而非其二进制输入长度,这属于伪多项式时间。若压缩为一维数组,容量必须从大到小遍历:
best[0..W] = 0
for each item i:
for k = W down to w[i]:
best[k] = max(best[k], value[i] + best[k - w[i]])
逆序更新使 best[k - w[i]] 仍代表上一件物品处理完后的结果;若从小到大更新,同一件物品可能被本轮重复使用,问题就会变成完全背包。
五、课后作业详解
1. 矩阵链乘法改为最大化(CLRS 15.3-3)
题意:矩阵链乘法通常通过选择括号化顺序,使标量乘法次数最少。若目标改成让标量乘法次数尽可能多,是否仍有最优子结构?
结论:仍具有最优子结构,可以用区间动态规划求最大代价。
设矩阵 $A_i$ 的维度为 $p_{i-1}\times p_i$。令 $M[i,j]$ 表示矩阵链 $A_iA_{i+1}\cdots A_j$ 的所有合法括号化中,最大的标量乘法次数。单个矩阵不需要相乘:
\[M[i,i]=0.\]对长度大于 1 的链,最后一次乘法必然在某个 $k$ 处分割成两条子链。左链结果维度为 $p_{i-1}\times p_k$,右链结果维度为 $p_k\times p_j$,最后相乘固定需要 $p_{i-1}p_kp_j$ 次标量乘法。因此:
\[M[i,j]=\max_{i\le k<j} \left(M[i,k]+M[k+1,j]+p_{i-1}p_kp_j\right).\]最优子结构证明:取一条整体最大代价的括号化方案,并固定其最后分割点 $k$。最后一次矩阵乘法的代价只由矩阵维度与 $k$ 决定,不受左右子链内部的括号化方式影响。假设左子链没有达到 $M[i,k]$,就可以用一条代价更大的左侧括号化替换它,右侧和最后一次乘法保持不变,整体代价随之增大,这与原方案已经最大矛盾。右子链同理。因此,固定 $k$ 时,左右子链都必须分别取最大代价;再枚举所有 $k$ 并取最大值,便覆盖了所有合法括号化方案。
数值例子:令 $A_1$ 为 $3\times5$、$A_2$ 为 $5\times2$、$A_3$ 为 $2\times7$。
\[(A_1A_2)A_3:\quad 3\cdot5\cdot2+3\cdot2\cdot7=30+42=72,\] \[A_1(A_2A_3):\quad 5\cdot2\cdot7+3\cdot5\cdot7=70+105=175.\]所以最大化问题选择 $A_1(A_2A_3)$,代价为 175。算法按区间长度从短到长填表,并记录达到最大值的分割点:
for i = 1..n:
M[i][i] = 0
for length = 2..n:
for i = 1..n-length+1:
j = i+length-1
M[i][j] = -infinity
for k = i..j-1:
candidate = M[i][k] + M[k+1][j] + p[i-1]*p[k]*p[j]
if candidate > M[i][j]:
M[i][j] = candidate
split[i][j] = k
状态数为 $O(n^2)$,每个区间最多枚举 $O(n)$ 个分割点,时间为 $O(n^3)$;代价表和分割表共需 $O(n^2)$ 空间。沿 split 表递归即可还原最大代价的括号化方案。
2. 求给定序列的一个 LCS(CLRS 15.4-1)
题目:
\[X=\langle1,0,0,1,0,1,0,1\rangle,\qquad Y=\langle0,1,0,1,1,0,1,1,0\rangle.\]求 $X$ 与 $Y$ 的一个最长公共子序列。
令 $C[i][j]$ 为两个前缀的 LCS 长度,并使用上一节的递推式。完整 DP 表如下,首行和首列对应空前缀:
| $i\backslash j$ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|
| $Y_j$ | 空 | 0 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | 0 |
| 0(空) | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1(1) | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 2(0) | 0 | 1 | 1 | 2 | 2 | 2 | 2 | 2 | 2 | 2 |
| 3(0) | 0 | 1 | 1 | 2 | 2 | 2 | 3 | 3 | 3 | 3 |
| 4(1) | 0 | 1 | 2 | 2 | 3 | 3 | 3 | 4 | 4 | 4 |
| 5(0) | 0 | 1 | 2 | 3 | 3 | 3 | 4 | 4 | 4 | 5 |
| 6(1) | 0 | 1 | 2 | 3 | 4 | 4 | 4 | 5 | 5 | 5 |
| 7(0) | 0 | 1 | 2 | 3 | 4 | 4 | 5 | 5 | 5 | 6 |
| 8(1) | 0 | 1 | 2 | 3 | 4 | 5 | 5 | 6 | 6 | 6 |
右下角 $C[8][9]=6$,所以最长公共子序列长度为 6。沿 DP 表回溯,可得到一个匹配位置序列:
\[(X_1,Y_2),(X_2,Y_3),(X_3,Y_6),(X_4,Y_7),(X_6,Y_8),(X_7,Y_9).\]对应的元素为:
\[\boxed{\langle1,0,0,1,1,0\rangle}.\]核对:它在 $X$ 中依次位于位置 $1,2,3,4,6,7$,在 $Y$ 中依次位于位置 $2,3,6,7,8,9$,因此确实是公共子序列。DP 表证明公共子序列长度不超过 6,而构造出的序列长度恰好为 6,所以它是一个 LCS。时间复杂度为 $O(mn)$,回溯为 $O(m+n)$。
3. 用 $O(n^2)$ 时间求最长递增子序列(CLRS 15.4-5)
题意:给定长度为 $n$ 的数字序列,设计 $O(n^2)$ 时间算法,找出最长单调递增子序列。
以下按“严格递增”解释,即相邻保留元素满足 $A[j]<A[i]$。如果课程采用“非递减”定义、允许相等元素,则把条件改为 $A[j]\le A[i]$。
令 $L[i]$ 表示必须以 $A[i]$ 结尾的最长严格递增子序列长度;令 prev[i] 保存该解中 $A[i]$ 的前驱位置。若某个子序列以 $A[i]$ 结尾,其前一个元素只能来自 $j<i$ 且 $A[j]<A[i]$,因此:
计算顺序为从左到右,因为状态 $L[i]$ 只依赖更早位置。算法如下:
for i = 1..n:
L[i] = 1
prev[i] = NIL
for j = 1..i-1:
if A[j] < A[i] and L[j] + 1 > L[i]:
L[i] = L[j] + 1
prev[i] = j
end = 任意一个使 L[end] 最大的位置
从 end 开始沿 prev 回溯并收集元素,最后反转
正确性说明:任意一个以 $A[i]$ 结尾、长度大于 1 的递增子序列,都有一个倒数第二个元素 $A[j]$,其中 $j<i$ 且 $A[j]<A[i]$。枚举所有这样的 $j$,取其中最大的 $L[j]$,就得到以 $A[i]$ 结尾的最长解。若该前缀不是以 $A[j]$ 结尾的最长递增子序列,就能用更长的同末尾子序列替换它,并在末尾接上 $A[i]$,得到更长解,矛盾。因此转移完整且不会遗漏最优解。最后在所有结尾位置中取最大的 $L[i]$,即为全局最长长度。
手算示例:对 $A=\langle3,1,2,2,5,4\rangle$,严格递增的状态为:
| 位置 $i$ | $A[i]$ | 一个最佳前驱 | $L[i]$ |
|---|---|---|---|
| 1 | 3 | 无 | 1 |
| 2 | 1 | 无 | 1 |
| 3 | 2 | 位置 2(值 1) | 2 |
| 4 | 2 | 位置 2(值 1) | 2 |
| 5 | 5 | 位置 3 或 4(值 2) | 3 |
| 6 | 4 | 位置 3 或 4(值 2) | 3 |
最大长度为 3,可恢复 $\langle1,2,5\rangle$ 或 $\langle1,2,4\rangle$。若允许相等,则 $\langle1,2,2,4\rangle$ 长度为 4。双层循环检查 $O(n^2)$ 对位置,时间复杂度为 $O(n^2)$;长度、前驱和输出数组使用 $O(n)$ 空间。
4. 用 $O(n\log n)$ 时间求最长递增子序列(CLRS 15.4-6)
题意:把上一题的时间降至 $O(n\log n)$。核心是维护各长度候选子序列的末尾,并通过输入位置之间的链接恢复答案。
直接枚举所有前驱需要 $O(n^2)$。加速的关键是:对同一长度,末尾值越小,后续能接上的元素只会越多,因此只保留该长度下最小的末尾值。
维护三个数组:
tailVal[k]:已扫描前缀中,长度为 $k+1$ 的递增子序列可能达到的最小末尾值。tailIdx[k]:实现tailVal[k]的输入位置。prev[i]:以位置 $i$ 结尾的候选序列的前驱位置。
严格递增时,tailVal 保持递增。处理新值 $x=A[i]$,用二分查找找出第一个满足 tailVal[p] >= x 的位置,即 lower_bound(x):
- 若 $p>0$,则
tailVal[p-1]<x,可把当前位置接到tailIdx[p-1]所代表的序列之后,令prev[i]=tailIdx[p-1]。 - 若 $p$ 恰好等于当前
tailVal长度,说明 $x$ 能延长目前最长候选,把它追加到末尾。 - 否则用 $x$ 替换
tailVal[p]。同长度候选中更小的末尾给未来留下更多扩展空间。
tailVal = 空数组
tailIdx = 空数组
prev[1..n] = NIL
for i = 1..n:
p = lower_bound(tailVal, A[i]) // 第一个 >= A[i] 的下标
if p > 0:
prev[i] = tailIdx[p-1]
if p == length(tailVal):
append A[i] to tailVal
append i to tailIdx
else:
tailVal[p] = A[i]
tailIdx[p] = i
end = tailIdx[length(tailIdx)-1]
从 end 开始沿 prev 回溯并收集 A[end],最后反转
为什么二分位置对应最长可接前缀:对长度 $1,2,\ldots$ 的候选,tailVal 记录的是各长度的最小末尾。若 tailVal[p-1]<x,长度 $p$ 的候选可以接上 $x$;而 tailVal[p]>=x(若存在)说明当前末尾还不能严格接上 $x$。由于末尾值有序,第一个不小于 $x$ 的位置恰好分隔了可扩展和不可扩展的长度。更新后,每个长度的最小末尾不增,数组仍保持有序。逐个处理完输入后,tailVal 的长度就是 LIS 长度。prev 链记录真实输入位置,保证输出的元素来自原序列且顺序正确。
用相等元素测试边界很重要。若要求非递减子序列(允许相等),二分位置应改为第一个严格大于 $x$ 的位置,即 upper_bound(x);只将严格条件换为非严格条件,而继续使用 lower_bound,就不会让相等元素延长答案。
仍以 $\langle3,1,2,2,5,4\rangle$ 为例,严格递增版本的 tailVal 变化如下:
| 处理位置和值 | 二分位置 $p$ | 更新后的 tailVal |
|---|---|---|
| $1:3$ | 0 | $[3]$ |
| $2:1$ | 0 | $[1]$ |
| $3:2$ | 1 | $[1,2]$ |
| $4:2$ | 1 | $[1,2]$,以新位置替换同值末尾 |
| $5:5$ | 2 | $[1,2,5]$ |
| $6:4$ | 2 | $[1,2,4]$ |
最后 tailVal 长度为 3。沿 tailIdx 和 prev 可恢复 $\langle1,2,4\rangle$。注意,其他输入下 tailVal 只表示各长度的最小尾值,它整体不一定对应一条真实子序列;因此题目要求输出具体序列时,不能只返回 tailVal,还必须保存位置链接。
每个元素做一次 $O(\log n)$ 二分与常数次更新,总时间为 $O(n\log n)$;tailVal、tailIdx、prev 和输出共需 $O(n)$ 空间。
六、本次课的主线
- 网格路径通过“从哪里到达当前格”构造计数转移。
- LCS 将两个前缀作为状态,按末尾元素是否相同决定匹配或跳过。
- 0-1 背包将“已考虑物品数”和“当前容量”作为状态维度,装与不装分别对应两个子问题。
- 矩阵链乘法即使从最小化改为最大化,仍保留同一套子链分解结构,只需改变聚合操作。
- LIS 的 $O(n^2)$ 解法枚举前驱;$O(n\log n)$ 解法压缩为每种长度一个最小末尾,再用二分查找和前驱链接恢复序列。
- 每次空间优化都必须根据依赖关系确定更新方向;0-1 背包的一维压缩需要容量逆序,避免重复使用当前物品。