6.4 经典模型——一个框架解决一族问题

问题情境：面试现场的编辑距离优化

连续三问的挑战

小明在面试时遇到了一道经典题：

第一问："实现编辑距离。"

小明自信地写出了 DP：

```python def edit_distance(X, Y): m, n = len(X), len(Y) dp = [[0] * (n + 1) for _ in range(m + 1)] for i in range(m + 1): dp[i][0] = i for j in range(n + 1): dp[0][j] = j for i in range(1, m + 1): for j in range(1, n + 1): if X[i-1] == Y[j-1]: dp[i][j] = dp[i-1][j-1] else: dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) return dp[m][n] ```

面试官点点头："运行正确。"

第二问："优化空间复杂度。"

小明想了想，用滚动数组：

```python def edit_distance_optimized(X, Y): m, n = len(X), len(Y) prev = list(range(n + 1)) curr = [0] * (n + 1) for i in range(1, m + 1): curr[0] = i for j in range(1, n + 1): if X[i-1] == Y[j-1]: curr[j] = prev[j-1] else: curr[j] = 1 + min(prev[j], curr[j-1], prev[j-1]) prev, curr = curr, prev return prev[n] ```

面试官："很好。"

第三问："如果要求的是 LCS（最长公共子序列），你的代码能改吗？"

小明愣住了："编辑距离和 LCS……递推式不一样，需要重新写代码。"

面试官："能不能用一个框架，解决这两种问题？甚至更多变体？"

小明陷入思考："一个框架……一族问题……"

困惑：为什么每个问题都要重新写代码？

小明发现：

编辑距离：三操作（插入、删除、替换）
LCS：禁止替换（或替换代价无穷）
子串匹配：自由起始位置

困惑：这些问题的结构相似，但每次都要重新写代码。能不能抽象出共同部分？

Skiena 的答案：可插拔桩函数框架

Steven Skiena 在《The Algorithm Design Manual》中提出了一个优雅的框架：

核心思想：一个 DP 表 + 四个可插拔桩函数。

```python def string_compare(X, Y): # DP 表 dp = [[0] * (len(Y) + 1) for _ in range(len(X) + 1)]

# 四个桩函数（可插拔）
row_init(dp)       # 初始化第一行
column_init(dp)    # 初始化第一列
match(c1, c2)      # 匹配/替换代价
goal_cell(dp)      # 终点位置

for i in range(len(X) + 1):
    for j in range(len(Y) + 1):
        # 状态转移（框架固定）
        ...

return goal_cell(dp)

```

关键：改桩函数 → 改问题。

直观思路：把共同部分抽象出来

编辑距离的共同结构

观察：所有编辑距离变体都有：

一个二维 DP 表
从左上角开始，向右下角填充
每个格子依赖三个邻居（左、上、左上）

差异：

初始化（第一行/列）：决定了起点约束
代价函数：决定了操作成本
终点：决定了终点约束

四个桩函数的作用

row_init：初始化第一行
- 编辑距离：dp[0][j] = j（从空串变成 Y[0:j]，需要 j 次插入）
- 子串匹配：dp[0][j] = 0（可以从任意位置开始匹配）
column_init：初始化第一列
- 编辑距离：dp[i][0] = i（从 X[0:i] 变成空串，需要 i 次删除）
- LCS：dp[i][0] = 0（空串与任意串的 LCS 是 0）
match：匹配/替换代价
- 编辑距离：若 c1 == c2，代价 0；否则代价 1（替换）
- LCS：若 c1 == c2，代价 0；否则代价 ∞（禁止替换）
goal_cell：终点位置
- 编辑距离：右下角 (m, n)
- 子串匹配：最后一行中 dp[i][j] 最小的位置

一个框架解决一族问题

问题	row_init	column_init	match	goal_cell
编辑距离	dp[0][j]=j	dp[i][0]=i	0 或 1	(m, n)
LCS	dp[0][j]=0	dp[i][0]=0	0 或 ∞	(m, n)
子串匹配	dp[0][j]=0	dp[i][0]=i	0 或 1	最后一行最小值
最长公共子串	dp[0][j]=0	dp[i][0]=0	0 或 -∞	表中最大值

关键洞察：框架不变，桩函数变化 → 问题变化。

规范定义：可插拔框架

框架结构

```python def dp_framework(X, Y, row_init, column_init, match, goal_cell): m, n = len(X), len(Y) dp = [[0] * (n + 1) for _ in range(m + 1)]

# 初始化
row_init(dp, n)
column_init(dp, m)

# 填表
for i in range(1, m + 1):
    for j in range(1, n + 1):
        cost = match(X[i-1], Y[j-1])
        dp[i][j] = min(
            dp[i-1][j-1] + cost,    # 匹配/替换
            dp[i-1][j] + 1,          # 删除
            dp[i][j-1] + 1           # 插入
        )

# 终点
return goal_cell(dp, m, n)

```

桩函数签名

```python def row_init(dp, n): """初始化第一行""" pass

def column_init(dp, m): """初始化第一列""" pass

def match(c1, c2): """匹配代价（0 表示匹配，>0 表示替换代价）""" pass

def goal_cell(dp, m, n): """终点位置，返回答案""" pass ```

算法实现：经典 DP 问题

导航：本节将按"状态维度演进"的顺序介绍经典 DP 问题。我们从一个状态（钢条切割）开始，逐步增加到两个状态（矩阵链乘、编辑距离、LCS），最后到更复杂的区间状态（最优BST）。每个问题都展示了状态设计的不同思路。

问题 1：钢条切割——从一维状态开始

状态维度演进位置：一维状态。这是最简单的 DP 结构，每个子问题只依赖更小的同类子问题。

问题：给定钢条长度价格表，求长度 n 的最优切割方案。

从朴素思路到 DP 的推理过程

第一次尝试：枚举所有切割方案

小明首先想到：把所有可能的切割方案都列出来，选收益最大的。

比如长度为 4 的钢条：

不切割：价格[4]
切一刀：[1,3], [2,2], [3,1]
切两刀：[1,1,2], [1,2,1], [2,1,1]
切三刀：[1,1,1,1]

困惑：切割方案数量随 n 指数增长！长度 10 就有 512 种方案。

第二次尝试：递归分解

小明换了个思路：第一刀切在哪里？

假设长度 n 的最优收益是 r(n)：

第一刀切 1：收益 = price[1] + r(n-1)
第一刀切 2：收益 = price[2] + r(n-2)
...
不切整根卖：收益 = price[n]

所以：r(n) = max(price[i] + r(n-i)) for i in 1..n

困惑：这还是递归，效率如何？

小明画出 r(4) 的递归树： ``` r(4) ├── price[1] + r(3) │ ├── price[1] + r(2) │ │ ├── price[1] + r(1) │ │ └── price[2] + r(0) │ ├── price[2] + r(1) │ └── price[3] + r(0) ├── price[2] + r(2) │ ├── price[1] + r(1) │ └── price[2] + r(0) ├── price[3] + r(1) │ └── price[1] + r(0) └── price[4] + r(0) ```

发现：r(2)、r(1) 被重复计算多次！

第三次尝试：记忆化递归

把算过的结果存起来，下次直接用：

```python def cut_rod_memo(price, n, memo=None): if memo is None: memo = {} if n in memo: return memo[n] if n == 0: return 0

max_val = 0
for i in range(1, n + 1):
    max_val = max(max_val, price[i] + cut_rod_memo(price, n - i, memo))
memo[n] = max_val
return max_val

```

成功：每个 r(i) 只算一次，总时间 O(n²)。

第四次优化：自底向上

小明意识到：既然 r(n) 依赖 r(0) 到 r(n-1)，不如从小到大算：

```python def cut_rod(price, n): dp = [0] * (n + 1) for i in range(1, n + 1): max_val = 0 for j in range(1, i + 1): max_val = max(max_val, price[j] + dp[i - j]) dp[i] = max_val return dp[n] ```

这就是 DP！

状态：dp[i] = 长度 i 的最优收益。

递推：dp[i] = max(price[j] + dp[i-j]) for j in 1..i

时间复杂度：O(n²)。

对比朴素递归：朴素递归是 O(φ^n)，DP 是 O(n²)。

过渡到矩阵链乘：钢条切割用一维状态就够了，因为我们只关心"切多长"。但有些问题需要同时考虑"从哪里开始"和"到哪里结束"，这就需要二维状态。矩阵链乘就是第一个例子。

问题 2：矩阵链乘——从一维到二维区间状态

状态维度演进位置：二维区间状态。钢条切割只有一个参数（长度），矩阵链乘需要两个参数（区间的起点和终点），因为我们需要追踪"哪些矩阵相乘"。

问题：给定矩阵维度序列，求最优括号化方案（最少乘法次数）。

状态：dp[i][j] = 矩阵 A_i..A_j 的最少乘法次数。

递推：dp[i][j] = min(dp[i][k] + dp[k+1][j] + p_{i-1}p_k p_j) for k in i..j-1

```python def matrix_chain(p): n = len(p) - 1 dp = [[0] * n for _ in range(n)]

for l in range(2, n + 1):
    for i in range(n - l + 1):
        j = i + l - 1
        dp[i][j] = float('inf')
        for k in range(i, j):
            cost = dp[i][k] + dp[k+1][j] + p[i] * p[k+1] * p[j+1]
            dp[i][j] = min(dp[i][j], cost)

return dp[0][n-1]

```

时间复杂度：O(n³)。

Knuth 优化：如何发现分割点单调性？

直觉铺垫：Knuth 优化不是"直接应用"的定理，而是需要观察和验证的性质。让我们通过一个具体例子，展示如何发现分割点的单调性。

问题设定：4 个矩阵 A₁A₂A₃A₄，维度序列 p = [10, 20, 30, 40, 50]。

这意味着：

A₁: 10×20
A₂: 20×30
A₃: 30×40
A₄: 40×50

第一步：计算所有 dp[i][j] 和最优分割点 s[i][j]

我们需要填充 DP 表。让我们从小区间开始：

长度 2 的区间（只有一种分割方式）：

区间	计算式	dp 值	分割点 s
[1,2]	dp[1][1] + dp[2][2] + 10×20×30 = 0 + 0 + 6000	6000	k=1
[2,3]	dp[2][2] + dp[3][3] + 20×30×40 = 0 + 0 + 24000	24000	k=2
[3,4]	dp[3][3] + dp[4][4] + 30×40×50 = 0 + 0 + 60000	60000	k=3

长度 3 的区间（两种分割方式）：

区间	分割 k=1	分割 k=2	最优 dp	最优 s
[1,3]	dp[1][1] + dp[2][3] + 10×20×40 = 0 + 24000 + 8000 = 32000	dp[1][2] + dp[3][3] + 10×30×40 = 6000 + 0 + 12000 = 18000	18000	k=2
[2,4]	dp[2][2] + dp[3][4] + 20×30×50 = 0 + 60000 + 30000 = 90000	dp[2][3] + dp[4][4] + 20×40×50 = 24000 + 0 + 40000 = 64000	64000	k=2

长度 4 的区间（三种分割方式）：

区间	分割 k=1	分割 k=2	分割 k=3	最优 dp	最优 s
[1,4]	dp[1][1]+dp[2][4]+10×20×50 = 0+64000+10000 = 74000	dp[1][2]+dp[3][4]+10×30×50 = 6000+60000+15000 = 81000	dp[1][3]+dp[4][4]+10×40×50 = 18000+0+20000 = 38000	38000	k=3

第二步：整理最优分割点表

让我们把最优分割点 s[i][j] 整理出来：

区间	s[i][j]
[1,2]	1
[2,3]	2
[3,4]	3
[1,3]	2
[2,4]	2
[1,4]	3

第三步：观察单调性

现在我们把分割点按"对角线方向"（相同区间长度）来看：

观察 s[1][2] 和 s[1][3] 和 s[1][4]：

s[1][2] = 1
s[1][3] = 2
s[1][4] = 3

当区间右端点 j 从 2 变成 4，最优分割点从 1 变成 3，单调递增。

观察 s[2][3] 和 s[2][4]：

s[2][3] = 2
s[2][4] = 2

当区间右端点 j 从 3 变成 4，最优分割点保持 2，单调不减。

观察 s[1][3] 和 s[2][4]：

s[1][3] = 2
s[2][4] = 2

当区间起点 i 从 1 变成 2，右端点 j 从 3 变成 4，最优分割点保持 2。

第四步：总结规律

单调性条件：

对于矩阵链乘，最优分割点满足： $$s[i][j-1] \leq s[i][j] \leq s[i+1][j]$$

直观理解：

当区间向右扩展时，最优分割点不会向左移
当区间向左扩展时，最优分割点不会向右移

为什么矩阵链乘满足单调性？

因为矩阵维度序列是固定的，每个矩阵的"大小"（行×列）相对稳定。当我们扩展区间时，新加入的矩阵会改变整体"形状"，但不会让之前的最优分割点变得"很差"——最多是"不够好"，需要向某个方向调整。

第五步：利用单调性优化

朴素算法：对于每个区间 [i,j]，遍历所有 k 从 i 到 j-1，时间 O(n³)。

优化算法：利用单调性，只搜索 s[i][j-1] 到 s[i+1][j] 的范围。

```python def matrix_chain_knuth(p): n = len(p) - 1 dp = [[0] * n for _ in range(n)] s = [[0] * n for _ in range(n)] # 最优分割点

# 初始化：长度为 1 的区间
for i in range(n):
    s[i][i] = i

for l in range(2, n + 1):
    for i in range(n - l + 1):
        j = i + l - 1
        dp[i][j] = float('inf')
        # 利用单调性：k 的范围缩小
        k_start = s[i][j-1] if l > 2 else i
        k_end = s[i+1][j] if l > 2 else j-1
        for k in range(k_start, k_end + 1):
            cost = dp[i][k] + dp[k+1][j] + p[i] * p[k+1] * p[j+1]
            if cost < dp[i][j]:
                dp[i][j] = cost
                s[i][j] = k

return dp[0][n-1]

```

时间复杂度分析：

朴素算法：对于长度为 l 的区间，搜索范围是 l-1 个位置。优化后：搜索范围被限制在 s[i][j-1] 到 s[i+1][j]，平均只有常数个位置。

总时间从 O(n³) 降到 O(n²)。

Knuth 优化的适用条件：

条件	说明
最优子结构	问题可以分解为子问题
单调性	最优分割点 s[i][j] 满足 s[i][j-1] ≤ s[i][j] ≤ s[i+1][j]
四边形不等式	区间 DP 的代价函数满足 w(i,j) + w(i',j') ≤ w(i,j') + w(i',j) 当 i ≤ i' ≤ j ≤ j'

验证方法：

先用小例子（如 4 个矩阵）手动计算 s 表
观察 s 表是否满足单调性
尝试证明（通常用四边形不等式）

过渡到编辑距离：矩阵链乘的二维状态是"区间状态"——两个参数定义一个区间。接下来看另一种二维状态："位置状态"——两个参数分别是两个字符串的位置。

问题 3：编辑距离——从区间状态到位置状态

状态维度演进位置：二维位置状态。矩阵链乘的二维状态是 [区间起点, 区间终点]，编辑距离的二维状态是 [字符串 X 的位置, 字符串 Y 的位置]。状态含义不同，但都是二维。

问题：给定字符串 X 和 Y，求最小编辑操作数。

状态：dp[i][j] = 将 X[0:i] 变成 Y[0:j] 的最小代价。

递推：

若 X[i] == Y[j]：dp[i][j] = dp[i-1][j-1]
否则：dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])

```python def edit_distance(X, Y): m, n = len(X), len(Y) dp = [[0] * (n + 1) for _ in range(m + 1)]

for i in range(m + 1):
    dp[i][0] = i
for j in range(n + 1):
    dp[0][j] = j

for i in range(1, m + 1):
    for j in range(1, n + 1):
        if X[i-1] == Y[j-1]:
            dp[i][j] = dp[i-1][j-1]
        else:
            dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])

return dp[m][n]

```

时间复杂度：O(mn)。

问题 4：最长公共子序列（LCS）——位置状态的变体

状态维度演进位置：二维位置状态（编辑距离变体）。LCS 可以看作"禁止替换"的编辑距离，状态结构相同，但转移规则不同。

问题：给定字符串 X 和 Y，求最长公共子序列长度。

状态：dp[i][j] = X[0:i] 和 Y[0:j] 的 LCS 长度。

递推：

若 X[i] == Y[j]：dp[i][j] = dp[i-1][j-1] + 1
否则：dp[i][j] = max(dp[i-1][j], dp[i][j-1])

```python def lcs(X, Y): m, n = len(X), len(Y) dp = [[0] * (n + 1) for _ in range(m + 1)]

for i in range(1, m + 1):
    for j in range(1, n + 1):
        if X[i-1] == Y[j-1]:
            dp[i][j] = dp[i-1][j-1] + 1
        else:
            dp[i][j] = max(dp[i-1][j], dp[i][j-1])

return dp[m][n]

```

时间复杂度：O(mn)。

过渡到最优 BST：编辑距离和 LCS 的二维状态是"位置状态"，每个状态对应一个位置对。但有些问题的状态需要更复杂的结构——最优 BST 的状态是"区间状态"，但需要额外追踪"谁是根节点"。

问题 5：最优二叉搜索树——从位置状态到更复杂的区间状态

状态维度演进位置：二维区间状态 + 额外选择。矩阵链乘是"区间状态 + 分割点选择"，最优 BST 是"区间状态 + 根节点选择"。状态含义更复杂，但结构相似。

问题：给定关键字及其搜索频率，求期望搜索代价最小的 BST。

入门例子：3 个键，感受"频率决定形状"

在介绍复杂的 DP 公式之前，让我们先用一个简单例子，手工枚举所有可能的 BST，感受为什么"频率决定形状"。

问题设定：

3 个键：K₁ < K₂ < K₃
搜索频率：f(K₁) = 0.3，f(K₂) = 0.2，f(K₃) = 0.5

关键概念：期望搜索代价 = Σ(深度 × 频率)

注意：在 BST 的代价计算中，深度从 1 开始（根节点深度为 1）。

枚举所有 BST 形状

形状 1：K₁ 为根 ``` K₁ (深度 1) \ K₂ (深度 2) \ K₃ (深度 3) ``` 期望代价 = 1×f(K₁) + 2×f(K₂) + 3×f(K₃) = 1×0.3 + 2×0.2 + 3×0.5 = 0.3 + 0.4 + 1.5 = 2.2

形状 2：K₁ 为根（右子树 K₃ 为根） ``` K₁ (深度 1) \ K₃ (深度 2) / K₂ (深度 3) ``` 期望代价 = 1×f(K₁) + 2×f(K₃) + 3×f(K₂) = 1×0.3 + 2×0.5 + 3×0.2 = 0.3 + 1.0 + 0.6 = 1.9

形状 3：K₂ 为根 ``` K₂ (深度 1) / \ K₁ K₃ (深度 2) ``` 期望代价 = 1×f(K₂) + 2×f(K₁) + 2×f(K₃) = 1×0.2 + 2×0.3 + 2×0.5 = 0.2 + 0.6 + 1.0 = 1.8

形状 4：K₃ 为根 ``` K₃ (深度 1) / K₂ (深度 2) / K₁ (深度 3) ``` 期望代价 = 1×f(K₃) + 2×f(K₂) + 3×f(K₁) = 1×0.5 + 2×0.2 + 3×0.3 = 0.5 + 0.4 + 0.9 = 1.8

形状 5：K₃ 为根（左子树 K₁ 为根） ``` K₃ (深度 1) / K₁ (深度 2) \ K₂ (深度 3) ``` 期望代价 = 1×f(K₃) + 2×f(K₁) + 3×f(K₂) = 1×0.5 + 2×0.3 + 3×0.2 = 0.5 + 0.6 + 0.6 = 1.7

对比分析

形状	根节点	期望代价	特点
形状 1	K₁	2.2	最高频键在最深
形状 2	K₁	1.9	第二频键在中间
形状 3	K₂	1.8	平衡树
形状 4	K₃	1.8	最高频键在根
形状 5	K₃	1.7	最优

关键洞察：

K₃ 频率最高（0.5），应该尽量靠近根
形状 5 把 K₃ 放在根，K₁ 放在第二层，K₂ 放在第三层
虽然 K₁ 频率比 K₂ 高，但由于 K₃ 在根，形状 5 比形状 4 更优

直觉：频率高的键应该"靠近根"，但"靠近根"不等于"深度最浅"——还要考虑左右子树的平衡。

状态：dp[i][j] = 关键字 i..j 构成 BST 的最小期望代价。

递推：dp[i][j] = min(dp[i][k-1] + dp[k+1][j] + w(i,j)) for k in i..j

其中 w(i,j) = Σ(freq[m]) for m in i..j，表示以 k 为根时，所有键的深度都增加 1，所以总代价增加 w(i,j)。

```python def optimal_bst(freq, n): dp = [[0] * n for _ in range(n)]

for i in range(n):
    dp[i][i] = freq[i]

for l in range(2, n + 1):
    for i in range(n - l + 1):
        j = i + l - 1
        dp[i][j] = float('inf')
        for k in range(i, j + 1):
            cost = (dp[i][k-1] if k > i else 0) + \
                   (dp[k+1][j] if k < j else 0) + \
                   sum(freq[i:j+1])
            dp[i][j] = min(dp[i][j], cost)

return dp[0][n-1]

```

时间复杂度：O(n³)。

路径重构：如何找回最优解？

为什么需要路径重构？

DP 表只存储最优值，不存储具体方案。

问题：知道"最优切割收益是 30"，但不知道"怎么切"。

方法：辅助表记录选择

钢条切割：

```python def cut_rod_with_solution(price, n): dp = [0] * (n + 1) choice = [0] * (n + 1) # 记录最优切割点

for i in range(1, n + 1):
    max_val = 0
    best_j = 0
    for j in range(1, i + 1):
        if price[j] + dp[i - j] > max_val:
            max_val = price[j] + dp[i - j]
            best_j = j
    dp[i] = max_val
    choice[i] = best_j

# 重构方案
solution = []
while n > 0:
    solution.append(choice[n])
    n -= choice[n]

return dp[n], solution

```

方法：回溯 DP 表

编辑距离：

```python def edit_distance_with_operations(X, Y): m, n = len(X), len(Y) dp = [[0] * (n + 1) for _ in range(m + 1)]

# 填表（略）
...

# 回溯
operations = []
i, j = m, n
while i > 0 or j > 0:
    if i > 0 and j > 0 and X[i-1] == Y[j-1]:
        operations.append('match')
        i -= 1
        j -= 1
    elif i > 0 and dp[i][j] == dp[i-1][j] + 1:
        operations.append('delete ' + X[i-1])
        i -= 1
    elif j > 0 and dp[i][j] == dp[i][j-1] + 1:
        operations.append('insert ' + Y[j-1])
        j -= 1
    else:
        operations.append('replace ' + X[i-1] + ' with ' + Y[j-1])
        i -= 1
        j -= 1

return dp[m][n], operations[::-1]

```

Knuth 优化：从 O(n³) 到 O(n²)

条件：最优分割点单调

定理：若最优分割点 k 满足单调性（即 dp[i][j] 的最优 k 随 j 增大而增大），可以优化。

证明（略）：利用单调性减少搜索范围。

应用：矩阵链乘

已在"问题 2"中详细说明，包括具体例子和单调性验证。

```python def matrix_chain_knuth(p): n = len(p) - 1 dp = [[0] * n for _ in range(n)] s = [[0] * n for _ in range(n)] # 最优分割点

for l in range(2, n + 1):
    for i in range(n - l + 1):
        j = i + l - 1
        dp[i][j] = float('inf')
        # 利用单调性：k 的范围缩小
        for k in range(s[i][j-1] if j > i + 1 else i, 
                      s[i+1][j] if j > i + 1 else j):
            cost = dp[i][k] + dp[k+1][j] + p[i] * p[k+1] * p[j+1]
            if cost < dp[i][j]:
                dp[i][j] = cost
                s[i][j] = k

return dp[0][n-1]

```

时间复杂度：O(n²)（利用单调性）。

正确性分析：剪贴证明

钢条切割的最优子结构

定理：设最优切割方案包含第一刀长度 i。则剩余部分（长度 n-i）的切割也是最优的。

证明（剪贴法）：

假设剩余部分的切割不是最优。

设最优切割方案为：长度 n-i 的最优切割收益 r* > 当前切割收益 r'。

构造新方案：第一刀长度 i + 剩余部分最优切割。

新收益：price[i] + r* > price[i] + r' = 当前最优收益。

矛盾。□

LCS 的最优子结构

定理：设 LCS 的最后一个字符是 X[i] = Y[j]。则 X[0:i-1] 和 Y[0:j-1] 的 LCS 也是最优的。

证明（略）：类似钢条切割，剪贴证明。

复杂度分析

经典 DP 问题复杂度表

问题	状态维度	状态数	转移代价	时间复杂度
钢条切割	一维	n	O(n)	O(n²)
矩阵链乘	二维（区间）	n²	O(n)	O(n³) → O(n²) Knuth
编辑距离	二维	mn	O(1)	O(mn)
LCS	二维	mn	O(1)	O(mn)
最优 BST	二维（区间）	n²	O(n)	O(n³)

变式与反例

变式 1：最长公共子串（必须是连续的）

区别：子串必须连续，子序列可以不连续。

状态设计：dp[i][j] = 以 X[i] 和 Y[j] 结尾的最长公共子串长度。

递推：

若 X[i] == Y[j]：dp[i][j] = dp[i-1][j-1] + 1
否则：dp[i][j] = 0

变式 2：带权编辑距离

区别：插入、删除、替换的代价不同。

修改 match 桩函数：

```python def weighted_match(c1, c2, insert_cost, delete_cost, replace_cost): if c1 == c2: return 0 else: return replace_cost ```

反例：贪心不能解 0-1 背包

原因：0-1 背包没有贪心选择性质。

示例：

物品：重量 (2, 3, 4)，价值 (3, 5, 6)
容量：5
贪心（按价值密度）：选物品 2（密度 5/3 ≈ 1.67），剩余容量 2，选物品 1，总价值 8
最优：选物品 3（价值 6）和物品 1（价值 3），总价值 9

常见错误诊断

错误 1：DP 表索引错误

```python

错误示例：索引从 1 开始，但字符串索引从 0 开始

dp[i][j] = dp[i-1][j-1] + 1 # 但 X[i] 应该是 X[i-1] ```

正确做法：dp[i][j] 对应 X[0:i-1]，即 X[i-1]。

错误 2：忘记初始化

```python

错误示例：编辑距离忘记初始化第一行/列

dp = [[0] * (n + 1) for _ in range(m + 1)]

缺少 dp[i][0] = i 和 dp[0][j] = j

```

后果：边界条件错误，导致结果不正确。

错误 3：Knuth 优化条件不满足

```python

错误示例：问题不满足单调性，强行用 Knuth 优化

结果：最优分割点范围错误，答案不正确

```

教训：Knuth 优化需要验证单调性条件。

LLM 连接：可插拔框架与 Prompt 设计

Prompt 的桩函数思维

类比：

DP 框架：核心逻辑不变
Prompt 框架：核心结构不变

桩函数对应：

row_init → Prompt 开头模板
column_init → Prompt 结尾模板
match → 任务描述
goal_cell → 输出格式

如何迁移框架思维到 Prompt 设计？

识别不变部分：Prompt 的核心结构
识别变化部分：任务特定的描述
设计桩函数：可插拔的模板片段
组合框架：不变 + 变化 → 完整 Prompt

练习

基本理解

概念解释：什么是"可插拔桩函数"？为什么能解决一族问题？
框架分析：分析编辑距离框架的四个桩函数，解释每个的作用。
画图验证：画出 LCS 的 DP 表填充过程，标注依赖关系。

方法应用

编辑距离实现：实现编辑距离，并扩展支持不同操作代价。
LCS 空间优化：实现 LCS 的滚动数组版本。
钢条切割路径重构：实现钢条切割的最优方案输出。

错误诊断

诊断错误：给定一个"忘记初始化"的 DP 代码，预测错误。
索引错误：如果 DP 表索引与字符串索引不一致，会发生什么？
Knuth 误用：有人在不满足单调性的问题上用 Knuth 优化，分析后果。

方案比较

编辑距离 vs LCS：对比两个问题的桩函数差异。
Knuth vs 普通矩阵链乘：对比两种实现的时间复杂度。
路径重构方法：对比辅助表和回溯两种方法。

开放设计

新问题框架设计：为"最长公共子串"设计可插拔框架。
Knuth 条件验证：验证矩阵链乘是否满足 Knuth 优化条件。
LLM 连接：设计一个 Prompt 的可插拔框架，类比 DP 框架。

综合应用

最优 BST 实现：实现最优 BST 的 DP，并输出最优树结构。
组合问题：设计一个新问题，用可插拔框架解决。
真实问题：用 DP 解决实际问题：最优股票买卖（最多 k 次交易）。

思考题

为什么可插拔框架能解决一族问题？

因为一族问题的核心结构相同，差异只在初始化、代价函数、终点。框架抽象出不变部分，桩函数处理变化部分。

如何验证 Knuth 优化的条件？

验证最优分割点的单调性：dp[i][j] 的最优 k 是否随 j 增大而增大。具体步骤见"矩阵链乘"章节的 4 矩阵例子。

路径重构为什么重要？

DP 表只存储最优值，不存储具体方案。路径重构找回最优解的具体步骤，是"知道答案"到"知道怎么做"的关键。

过渡：掌握了经典 DP 模型，理解了框架思维。下一节：DP 与 LLM 推理的同构性——记忆化与 KV-Cache 的连接。

参考文献：

Cormen T H, et al. Introduction to Algorithms[M]. 4th ed. MIT Press, 2022. Chapter 15.
Skiena S S. The Algorithm Design Manual[M]. 3rd ed. Springer, 2020. Chapter 10.
Kleinberg J, Tardos E. Algorithm Design[M]. Pearson, 2005. Chapter 6.

6.4 经典模型——一个框架解决一族问题 ​

问题情境：面试现场的编辑距离优化 ​

连续三问的挑战 ​

困惑：为什么每个问题都要重新写代码？ ​

Skiena 的答案：可插拔桩函数框架 ​

直观思路：把共同部分抽象出来 ​

编辑距离的共同结构 ​

四个桩函数的作用 ​

一个框架解决一族问题 ​

规范定义：可插拔框架 ​

框架结构 ​

桩函数签名 ​

算法实现：经典 DP 问题 ​

问题 1：钢条切割——从一维状态开始 ​

从朴素思路到 DP 的推理过程 ​

问题 2：矩阵链乘——从一维到二维区间状态 ​

Knuth 优化：如何发现分割点单调性？ ​

问题 3：编辑距离——从区间状态到位置状态 ​

问题 4：最长公共子序列（LCS）——位置状态的变体 ​

问题 5：最优二叉搜索树——从位置状态到更复杂的区间状态 ​

入门例子：3 个键，感受"频率决定形状" ​

路径重构：如何找回最优解？ ​

为什么需要路径重构？ ​

方法：辅助表记录选择 ​

方法：回溯 DP 表 ​

Knuth 优化：从 O(n³) 到 O(n²) ​

条件：最优分割点单调 ​

应用：矩阵链乘 ​

正确性分析：剪贴证明 ​

钢条切割的最优子结构 ​

LCS 的最优子结构 ​

复杂度分析 ​

经典 DP 问题复杂度表 ​

变式与反例 ​

变式 1：最长公共子串（必须是连续的） ​

变式 2：带权编辑距离 ​

反例：贪心不能解 0-1 背包 ​

常见错误诊断 ​

错误 1：DP 表索引错误 ​

错误示例：索引从 1 开始，但字符串索引从 0 开始 ​

错误 2：忘记初始化 ​

错误示例：编辑距离忘记初始化第一行/列 ​

缺少 dp[i][0] = i 和 dp[0][j] = j ​

错误 3：Knuth 优化条件不满足 ​

错误示例：问题不满足单调性，强行用 Knuth 优化 ​

结果：最优分割点范围错误，答案不正确 ​

LLM 连接：可插拔框架与 Prompt 设计 ​

Prompt 的桩函数思维 ​

如何迁移框架思维到 Prompt 设计？ ​

练习 ​

基本理解 ​

方法应用 ​

错误诊断 ​

方案比较 ​

开放设计 ​

综合应用 ​

思考题 ​

6.4 经典模型——一个框架解决一族问题

问题情境：面试现场的编辑距离优化

连续三问的挑战

困惑：为什么每个问题都要重新写代码？

Skiena 的答案：可插拔桩函数框架

直观思路：把共同部分抽象出来

编辑距离的共同结构

四个桩函数的作用

一个框架解决一族问题

规范定义：可插拔框架

框架结构

桩函数签名

算法实现：经典 DP 问题

问题 1：钢条切割——从一维状态开始

从朴素思路到 DP 的推理过程

问题 2：矩阵链乘——从一维到二维区间状态

Knuth 优化：如何发现分割点单调性？

问题 3：编辑距离——从区间状态到位置状态

问题 4：最长公共子序列（LCS）——位置状态的变体

问题 5：最优二叉搜索树——从位置状态到更复杂的区间状态

入门例子：3 个键，感受"频率决定形状"

路径重构：如何找回最优解？

为什么需要路径重构？

方法：辅助表记录选择

方法：回溯 DP 表

Knuth 优化：从 O(n³) 到 O(n²)

条件：最优分割点单调

应用：矩阵链乘

正确性分析：剪贴证明

钢条切割的最优子结构

LCS 的最优子结构

复杂度分析

经典 DP 问题复杂度表

变式与反例

变式 1：最长公共子串（必须是连续的）

变式 2：带权编辑距离

反例：贪心不能解 0-1 背包

常见错误诊断

错误 1：DP 表索引错误

错误示例：索引从 1 开始，但字符串索引从 0 开始

错误 2：忘记初始化

错误示例：编辑距离忘记初始化第一行/列

缺少 dp[i][0] = i 和 dp[0][j] = j

错误 3：Knuth 优化条件不满足

错误示例：问题不满足单调性，强行用 Knuth 优化

结果：最优分割点范围错误，答案不正确

LLM 连接：可插拔框架与 Prompt 设计

Prompt 的桩函数思维

如何迁移框架思维到 Prompt 设计？

练习

基本理解

方法应用

错误诊断

方案比较

开放设计

综合应用

思考题