6.3 状态设计——从一维到多维的平衡
问题情境：状态爆炸的困境
面试现场的内存溢出
小明在面试时遇到一道 DP 题：
问题：给定字符串 X 和 Y，求最长公共子序列（LCS）。
小明很快写出了二维 DP：
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]面试官点点头："字符串长度 1000，你的空间复杂度是多少？"
小明："dp 表是 (m+1) × (n+1)，空间 O(mn)。"
面试官继续："如果 m = n = 10000，dp 表需要多少内存？"
小明计算：10001 × 10001 × 4 字节（int） ≈ 400 MB。
面试官："你的程序内存限制是 100 MB，怎么办？"
小明愣住了："空间不够……怎么优化？"
第一次困惑：状态维度与空间的关系
小明发现：状态维度越高，空间越大。
| 状态维度 | 空间复杂度 | 示例问题 |
|---|---|---|
| 一维 | O(n) | Fibonacci |
| 二维 | O(n²) | LCS、编辑距离 |
| 三维 | O(n³) | 某些区间 DP |
| n 维 | O(2^n) | TSP |
困惑：如何在高维状态中压缩空间？
第二次困惑：维度太少无法刻画子问题
小明尝试把 LCS 优化到一维：
# 错误尝试：只保留一行
def lcs_wrong(X, Y):
dp = [0] * (len(Y) + 1)
for i in range(1, len(X) + 1):
for j in range(1, len(Y) + 1):
if X[i-1] == Y[j-1]:
dp[j] = dp[j-1] + 1 # 错误！dp[j-1] 是当前行的值
else:
dp[j] = max(dp[j], dp[j-1])
return dp[len(Y)]运行后，结果错误。
问题：dp[j-1] 在更新时已经是当前行的值，不是上一行的值。
小明困惑："维度太少，无法正确刻画子问题依赖关系。怎么平衡？"
第三次改进：滚动数组
小明查阅资料，发现滚动数组技术：
def lcs_rolling(X, Y):
m, n = len(X), len(Y)
# 只保留两行：prev（上一行）和 curr（当前行）
prev = [0] * (n + 1)
curr = [0] * (n + 1)
for i in range(1, m + 1):
for j in range(1, n + 1):
if X[i-1] == Y[j-1]:
curr[j] = prev[j-1] + 1
else:
curr[j] = max(prev[j], curr[j-1])
prev, curr = curr, prev # 滚动交换
return prev[n]测试：m = n = 10000，空间 2 × 10001 × 4 ≈ 80 KB。
效率提升：400 MB → 80 KB。5000 倍压缩。
直观思路：状态是什么？
状态的本质
定义：状态是描述子问题的参数组合。
示例：
- Fibonacci：状态 fib(i) 由参数 i 确定 → 一维
- LCS：状态 dp[i][j] 由参数 i 和 j 确定 → 二维
- 矩阵链乘：状态 m[i][j] 由参数 i 和 j 确定（区间）→ 二维
状态设计的三原则
- 唯一性：每个状态唯一确定一个子问题
- 完备性：所有子问题都能被状态覆盖
- 依赖性：状态之间有清晰的依赖关系
状态维度与空间的关系
| 状态维度 | 参数数量 | 状态空间大小 |
|---|---|---|
| 一维 | 1 | O(n) |
| 二维 | 2 | O(n²) |
| 三维 | 3 | O(n³) |
| ... |
空间爆炸：维度增加，空间指数增长。
规范定义：状态空间与状态转移
状态空间的定义
定义：状态空间是所有可能状态组成的集合。
大小：|状态空间| = 各参数取值范围的乘积。
示例：
- Fibonacci：参数 i ∈ [0, n]，状态空间大小 n+1
- LCS：参数 i ∈ [0, m]，j ∈ [0, n]，状态空间大小 (m+1)(n+1)
状态转移方程
定义：描述如何从已知状态计算新状态的方程。
形式：dp[新状态] = f(dp[依赖状态])
示例：
- Fibonacci：dp[i] = dp[i-1] + dp[i-2]
- LCS：dp[i][j] = dp[i-1][j-1] + 1（若 X[i] = Y[j]）
初始条件与边界
初始条件：状态空间中已知的初始值。
边界条件：状态转移中需要处理的特殊情况。
示例：
- Fibonacci：dp[0] = 0, dp[1] = 1（初始条件）
- LCS：dp[i][0] = 0, dp[0][j] = 0（边界条件）
算法实现：从一维到三维
一维状态：Fibonacci
def fib(n):
if n <= 1:
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]状态：dp[i]，一维。 空间优化：只保留前两个值，O(1) 空间。
二维状态：LCS
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]状态：dp[i][j]，二维。 空间优化：滚动数组，只保留两行，O(n) 空间。
三维状态：区间 DP（矩阵链乘）
def matrix_chain(p):
n = len(p) - 1
dp = [[0] * n for _ in range(n)]
# l 是链长度
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]状态：dp[i][j]，二维（但隐含长度 l，实际上是三维）。 空间：O(n²)。
高维状态：TSP（状态压缩）
def tsp_dp(dist):
n = len(dist)
# dp[S][i] = 已访问集合 S，当前在 i 的最短路径
dp = [[float('inf')] * n for _ in range(2**n)]
dp[1][0] = 0 # 起点
for S in range(1, 2**n):
for i in range(n):
if S & (1 << i): # i 在集合 S 中
for j in range(n):
if not (S & (1 << j)): # j 未访问
dp[S | (1 << j)][j] = min(
dp[S | (1 << j)][j],
dp[S][i] + dist[i][j]
)
# 回到起点
full = 2**n - 1
return min(dp[full][i] + dist[i][0] for i in range(n))状态：dp[S][i]，其中 S 是集合（状态压缩为整数）。 状态空间大小：2^n × n。 空间：O(n × 2^n)。
状态压缩技术
滚动数组
适用场景：递推式只依赖前几行/列。
原理：只保留必要的行/列，不保留整个表。
示例：LCS 的滚动数组（只保留两行）。
状态压缩（位运算）
适用场景：状态中包含集合。
原理：用整数表示集合，每个 bit 表示元素是否在集合中。
示例：TSP 的 dp[S]，其中 S 是访问过的城市集合。
空间换时间的权衡
| 技术 | 空间优化 | 适用条件 |
|---|---|---|
| 滚动数组 | O(n²) → O(n) | 递推式只依赖前几行 |
| 状态压缩 | O(n! × n) → O(2^n × n) | 状态包含集合 |
| 一维优化 | O(n) → O(1) | 只需前一状态 |
正确性分析：状态设计是否完备？
状态完备性验证
原则：每个子问题都能被某个状态覆盖。
检验方法：
- 列出所有可能的子问题
- 检查是否每个子问题都有对应状态
- 若有遗漏，补充状态
示例：LCS 的子问题是"前缀 X[0:i] 和 Y[0:j] 的 LCS"，状态 dp[i][j] 完备覆盖。
状态唯一性验证
原则：同一个子问题不能被多个状态描述（否则冗余）。
检验方法：检查参数组合是否有重复。
复杂度分析
时间复杂度的状态视角
公式：时间复杂度 = O(状态数 × 每个状态的转移代价)。
示例：
- Fibonacci：状态数 n，转移代价 O(1)，时间 O(n)
- LCS：状态数 mn，转移代价 O(1)，时间 O(mn)
- 矩阵链乘：状态数 n²，转移代价 O(n)，时间 O(n³)
- TSP：状态数 2^n × n，转移代价 O(n)，时间 O(n² × 2^n)
空间复杂度的状态视角
公式：空间复杂度 = O(状态数)（若不优化）。
优化后：空间复杂度 = O(必需状态数)。
示例：
- LCS：状态数 mn，优化后 O(n)
- Fibonacci：状态数 n，优化后 O(1)
反例与变式
反例 1：状态维度太少
问题：最长公共子串（必须是连续的）。
错误设计：用 LCS 的二维状态。
正确设计：需要额外标记"当前匹配长度"，可能需要三维状态。
反例 2：状态维度太多
问题：某问题设计了 5 维状态，空间 O(n^5)。
教训：n=10 时，空间 10^5 = 100000，还好。n=100 时，空间 10^10 = 10 billion，爆炸。
改进：寻找冗余维度，或用滚动数组。
变式：带权 LCS
问题：字符有权重，求权重之和最大的 LCS。
状态设计：dp[i][j] = 前缀 X[0:i] 和 Y[0:j] 的带权 LCS 最大权重。
递推式：类似 LCS，但 +1 改为 +weight[X[i]]。
常见错误诊断
错误 1：状态定义不唯一
# 错误示例：同一子问题有多个状态
dp[i][j][k] = ... # 但实际上 k 由 i 和 j 决定，冗余后果：空间浪费，甚至可能导致计算顺序混乱。
错误 2：滚动数组方向错误
# 错误示例：LCS 滚动数组方向错误
for j in range(1, n + 1):
if X[i-1] == Y[j-1]:
dp[j] = dp[j-1] + 1 # 错误！dp[j-1] 是当前行，不是上一行正确做法：需要两个数组 prev 和 curr，避免混淆。
错误 3：状态压缩范围错误
# 错误示例：状态压缩的范围不够
dp = [[...] for _ in range(2**n)] # 但某些状态不需要，浪费空间改进：只存储可达状态。
LLM 连接：Prompt 设计与状态设计
Prompt 的状态维度
类比：
- DP 状态：参数组合，决定子问题
- LLM Prompt：输入组合，决定输出
相似问题：
- Prompt 太长 → LLM 处理慢（类似状态维度太多）
- Prompt 不完备 → LLM 无法正确回答（类似状态不完备）
如何迁移 DP 思维到 Prompt 设计？
- 最小必要信息：类似状态的最小维度，只保留必要信息
- 避免冗余：类似状态的唯一性，避免重复描述
- 分层 Prompt：类似滚动数组，分阶段处理
练习
基本理解
概念解释：什么是"状态"？如何判断状态维度？
状态分析：分析 LCS 的状态为什么需要二维，不能压缩到一维？
画图验证：画出 LCS 的状态转移图，标注依赖关系。
方法应用
滚动数组实现：实现 LCS 的滚动数组版本，对比空间复杂度。
状态压缩实现：实现 TSP 的状态压缩 DP，分析状态空间大小。
新问题状态设计：为"最长公共子串"设计状态。
错误诊断
诊断错误：给定一个"状态定义不唯一"的 DP，分析问题。
滚动数组错误：如果 LCS 滚动数组只用一个数组，会发生什么错误？
状态压缩误判：有人用状态压缩解非集合问题，分析错误。
方案比较
一维 vs 二维：对比 Fibonacci 和 LCS 的状态维度差异。
滚动 vs 状态压缩：对比两种空间优化技术的适用场景。
状态设计权衡：如何在维度与空间之间权衡？
开放设计
新问题状态设计：为"编辑距离"设计状态，写出递推式。
空间优化创新：设计一个新问题的空间优化方案。
LLM 连接：分析 Prompt 的"状态维度"，类比 DP 状态设计。
综合应用
矩阵链乘状态分析：分析矩阵链乘的状态为什么是二维（隐含三维）。
区间 DP 设计：为"石子合并"设计状态。
真实问题：用 DP 解决实际问题：最优股票买卖（带冷却期）。
思考题
状态维度与空间的关系？
状态维度越多，空间越大（指数增长）。但维度太少，无法正确刻画子问题依赖。需要平衡。
何时用滚动数组？何时用状态压缩？
- 滚动数组：递推式只依赖前几行/列
- 状态压缩：状态包含集合（如 TSP）
状态设计的三原则？
- 唯一性：每个状态唯一确定一个子问题
- 完备性：所有子问题都能被状态覆盖
- 依赖性：状态之间有清晰的依赖关系
过渡：掌握了状态设计，就可以解决经典 DP 模型。下一节：一个框架解决一族问题——可插拔桩函数的威力。
参考文献：
- 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.