动态规划基础
动态规划（Dynamic Programming, DP）把优化问题拆成重叠子问题，按拓扑顺序填表求解。曼哈顿游客问题是它的直观模型，也是序列比对的直接前身。
- DP 三要素：最优子结构、重叠子问题、无后效性
- 曼哈顿游客问题把 DP 直观化为网格上的最长路径
- 从规则网格推广到 DAG，得到通用的最长路径递推
- 序列比对就是加了对角线移动的曼哈顿游客问题
什么是动态规划
Section titled “什么是动态规划”动态规划是一种算法设计技术，用于解决具有以下特征的问题：
- 最优子结构：问题的最优解包含其子问题的最优解
- 重叠子问题：递归算法会反复求解相同的子问题
- 无后效性：一旦某个子问题的解确定，它不会受到后续决策的影响
动态规划通过存储子问题的解来避免重复计算，从而将指数级复杂度降低到多项式级。
曼哈顿游客问题
Section titled “曼哈顿游客问题”想象你在曼哈顿的街道网格中旅行，只能向南或向东移动。每个街区（block）都有一个"吸引力值"（attraction score），表示该街区值得参观的程度。
问题：从西南角 出发，到达东北角 ，找到一条能访问最多吸引力的路径。
给定一个 的网格：
- 每个垂直边（南北向）有权重
- 每个水平边（东西向）有权重
- 游客从 出发，只能向南或向东移动
- 目标：找到从 到 的路径，使路径上边的权重之和最大
与生物信息学的联系
Section titled “与生物信息学的联系”曼哈顿游客问题是序列比对（Sequence Alignment）的抽象模型。比较两条 DNA、RNA 或蛋白质序列、找出最优对应关系，搜索空间随序列长度呈指数增长，而动态规划将其降为多项式时间。
通过将序列比对映射为网格路径问题，曼哈顿游客问题为以下任务提供统一框架：
- 全局比对：对齐两条完整序列（Needleman-Wunsch 算法）
- 局部比对：寻找两条序列中最相似的子区域（Smith-Waterman 算法）
- 重叠比对：寻找两条序列末端的重叠区域（用于基因组组装）
动态规划解法
Section titled “动态规划解法”不直接求解从 到 的最长路径，而是求解一个更一般的问题：
找到从 到任意位置 的最长路径，记为 。
虽然这看起来像是要解决 个问题而不是 1 个，但求解这些子问题反而更容易，因为它们可以递推地解决。
要到达位置 ，游客只有两种方式：
- 从 向南移动
- 从 向东移动
s_{0,0} &= 0 \\ s_{i,0} &= s_{i-1,0} + \text{down}[i,0] \quad \text{（只能向南）} \\ s_{0,j} &= s_{0,j-1} + \text{right}[0,j] \quad \text{（只能向东）} \end{aligned}$$ ### 伪代码 ```text MANHATTANTOURIST(down, right, n, m) 1 s[0,0] ← 0 2 for i ← 1 to n 3 s[i,0] ← s[i-1,0] + down[i,0] 4 for j ← 1 to m 5 s[0,j] ← s[0,j-1] + right[0,j] 6 for i ← 1 to n 7 for j ← 1 to m 8 s[i,j] ← max(s[i-1,j] + down[i,j], 9 s[i,j-1] + right[i,j]) 10 return s[n,m] ``` ## Worked Example 考虑一个 $3 \times 3$ 的网格，权重如下： **垂直边权重 down**（从上方到下方）： | | j=0 | j=1 | j=2 | j=3 | | :--- | :--- | :--- | :--- | :--- | | i=1 | 1 | 2 | 3 | 1 | | i=2 | 2 | 1 | 2 | 3 | | i=3 | 3 | 2 | 1 | 2 | **水平边权重 right**（从左方到右方）： | | j=1 | j=2 | j=3 | | :--- | :--- | :--- | :--- | | i=0 | 3 | 2 | 4 | | i=1 | 1 | 4 | 2 | | i=2 | 2 | 1 | 3 | | i=3 | 1 | 3 | 2 | ### 初始化边界 ```text s[0,0] = 0 第一列（只能从上方来）： s[1,0] = 0 + 1 = 1 s[2,0] = 1 + 2 = 3 s[3,0] = 3 + 3 = 6 第一行（只能从左方来）： s[0,1] = 0 + 3 = 3 s[0,2] = 3 + 2 = 5 s[0,3] = 5 + 4 = 9 ``` ### 填充内部 ```text s[1,1] = max(3 + 2, 1 + 1) = 5 ← 从上方 s[1,2] = max(5 + 3, 5 + 4) = 9 ← 从左方 s[1,3] = max(9 + 1, 9 + 2) = 11 ← 从左方 s[2,1] = max(5 + 1, 3 + 2) = 6 ← 从上方 s[2,2] = max(9 + 2, 6 + 1) = 11 ← 从上方 s[2,3] = max(11 + 3, 11 + 3) = 14 ← 两者等价 s[3,1] = max(6 + 2, 6 + 1) = 8 ← 从上方 s[3,2] = max(11 + 1, 8 + 3) = 12 ← 从上方 s[3,3] = max(14 + 2, 12 + 2) = 16 ← 从上方 ``` ### 完整 DP 表 ```text j=0 j=1 j=2 j=3 i=0 0 3 5 9 i=1 1 5 9 11 i=2 3 6 11 14 i=3 6 8 12 16 ``` **最大权重路径**：从 $(0,0)$ 到 $(3,3)$ 的最大权重为 $16$。 ### 路径回溯 从终点 $(3,3)$ 反向追踪每一步的选择，恢复最优路径： ```text (3,3) ← 上方(2,3) ← 上方(1,3) ← 左方(1,2) ← 上方(0,2) ← 左方(0,1) ← 左方(0,0) ``` 路径：$(0,0) \to (0,1) \to (0,2) \to (1,2) \to (1,3) \to (2,3) \to (3,3)$ 回溯伪代码： ```text BACKTRACK(s, n, m) 1 i ← n, j ← m 2 path ← [] 3 while i > 0 or j > 0 4 if i > 0 and s[i,j] == s[i-1,j] + down[i,j] 5 path ← append("south", path) 6 i ← i - 1 7 else if j > 0 and s[i,j] == s[i,j-1] + right[i,j] 8 path ← append("east", path) 9 j ← j - 1 10 return path ``` ## 从网格到 DAG 曼哈顿是规则网格，但生物学问题中的路径可能更复杂。任何网格或比对图都可以抽象为 **DAG（Directed Acyclic Graph, 有向无环图）**。 ### 核心概念 <DefinitionList items={[ { term: '入度（Indegree）', definition: '进入一个顶点的边数。在 DP 中，入度决定了该顶点的前驱数量。', }, { term: '出度（Outdegree）', definition: '从一个顶点出去的边数。', }, { term: '前驱（Predecessors）', definition: '所有能直接到达顶点 $v$ 的顶点集合 $P(v)$。DP 递推中需要遍历所有前驱。', }, ]} /> ### DAG 中的最长路径递推 对于任意顶点 $v$，其得分 $s_v$ 为： $$s_v = \max_{u \in P(v)} \{ s_u + \text{weight}(u, v) \}$$ 这是通用的递推公式。在曼哈顿网格中，$P(i,j) = \{(i-1,j), (i,j-1)\}$，每个顶点恰好 2 个前驱。在通用 DAG 中，前驱数量可以任意。 ### 拓扑排序 为了确保计算 $s_v$ 时所有前驱 $s_u$ 已计算完毕，需要按**拓扑排序**顺序遍历顶点。 **定义**：拓扑排序是 DAG 中顶点的线性排列，使得对于每条有向边 $(u, v)$，$u$ 在排列中出现在 $v$ 之前。 - 在规则网格中，按行、按列或按对角线遍历都是合法的拓扑排序 - 在通用 DAG 中，拓扑排序保证所有边的方向都是从序号小的顶点指向序号大的顶点 - 拓扑排序可用 Kahn 算法（基于入度的 BFS）或 DFS 在 $O(|V| + |E|)$ 时间内完成 ```text TOPOLOGICALSORT(G) 1 计算每个顶点的入度 2 将所有入度为 0 的顶点放入队列 Q 3 order ← [] 4 while Q 不为空 5 v ← Q.dequeue() 6 将 v 追加到 order 7 for each 邻接顶点 w of v 8 删除边（v, w） 9 if w 的入度变为 0 10 Q.enqueue(w) 11 return order ``` ## 一维例子：找零问题 除了网格类问题，动态规划也适用于一维优化问题。找零问题（Change Problem）展示了 DP 如何优化递归解法。 ### 问题描述 给定金额 $M$ 和硬币面额 $c = (c_1, c_2, \ldots, c_d)$，用最少数量的硬币凑出金额 $M$。 ### 贪心为何不够 在日常币制下"优先取最大面额"的贪心策略通常有效，但在任意币值下会失效。设 $M = 40$、$c = \{25, 20, 1\}$： - **贪心解**：先取 25，剩余 15 只能用 1 凑，共 $1 + 15 = 16$ 枚； - **最优解**：取 2 个 20，共 $2$ 枚。 贪心只顾眼前最大面额，错过了更优的组合。动态规划通过保存每个金额 $m$ 的最少硬币数，确保得到全局最优。 ### 递推关系 ```text bestNumCoins[m] = min( bestNumCoins[m - c₁] + 1, bestNumCoins[m - c₂] + 1, ..., bestNumCoins[m - c_d] + 1 ) 对于所有 m ≥ cᵢ ``` ### 自底向上算法 ```text DPCHANGE(M, c, d) 1 bestNumCoins[0] ← 0 2 for m ← 1 to M 3 bestNumCoins[m] ← ∞ 4 for i ← 1 to d 5 if m ≥ cᵢ 6 if bestNumCoins[m - cᵢ] + 1 < bestNumCoins[m] 7 bestNumCoins[m] ← bestNumCoins[m - cᵢ] + 1 8 return bestNumCoins[M] ``` **复杂度**：时间 $O(M \times d)$，空间 $O(M)$。 关键在于从 0 开始递增计算到 $M$，保证计算 `bestNumCoins[m]` 时所有需要的子问题都已解决，每个子问题只计算一次。 ## 与序列比对的联系 曼哈顿游客问题与序列比对有着直接对应关系： | 网格元素 | 比对含义 | 分数 | | :--- | :--- | :--- | | 顶点 $(i, j)$ | 序列 1 的前 $i$ 个字符与序列 2 的前 $j$ 个字符对齐 | -- | | 水平边（向右） | 在序列 2 中插入一个空位（Gap） | $-\delta$（空位罚分） | | 垂直边（向下） | 在序列 1 中插入一个空位（Gap） | $-\delta$（空位罚分） | | 对角线移动 | 匹配（Match）或错配（Mismatch） | $+1$（匹配）或 $-\mu$（错配） | 经典比对算法都是曼哈顿游客问题的扩展： - **Needleman-Wunsch（1970）**：增加对角线移动，用于全局比对，递推变为三方向取最大值 - **Smith-Waterman（1981）**：增加"从零开始"选项（$s_{i,j}$ 可取 $0$），用于局部比对 - **Gotoh（1982）**：引入仿射空位罚分（Affine Gap Penalty），DP 矩阵扩展为三个 ## 与真实工具的连接 现代比对工具并不直接运行完整的 Needleman-Wunsch DP（对长序列太慢），而是使用种子-扩展（Seed-and-Extend）策略： 1. **种子阶段**：通过索引（如 FM-Index）快速找到精确匹配的短片段 2. **扩展阶段**：在种子周围使用带空位罚分的 DP 进行局部精确对齐 3. **评分阶段**：根据 DP 得分和映射质量（MapQ）评估比对结果可信度 核心仍然是动态规划，只是限制在局部小范围内运行，从而实现基因组尺度的高效比对。 ## 复杂度与适用前提 | 步骤 | 时间复杂度 | 空间复杂度 | | :--- | :--- | :--- | | 初始化边界 | $O(n + m)$ | $O(nm)$ | | 填充 DP 表 | $O(nm)$ | $O(nm)$ | | 路径回溯 | $O(n + m)$ | $O(n + m)$（路径长度） | | **总计** | **$O(nm)$** | **$O(nm)$** | 对于序列比对，如果两条序列长度分别为 $n$ 和 $m$，复杂度为 $O(nm)$。对于人类基因组级别数据（$n \approx m \approx 3 \times 10^9$），完整 DP 表需要约 $9 \times 10^{18}$ 个单元格，实践中不可行。这正是 BWA、minimap2 等工具使用种子-扩展策略的原因。 ### 空间优化 如果只需要最优路径权重而不需要路径本身，可将空间复杂度从 $O(nm)$ 降到 $O(\min(n, m))$，因为计算第 $i$ 行时只需要第 $i-1$ 行的结果。 如果需要恢复路径本身，可使用 **Hirschberg 算法**，利用分治法在 $O(nm)$ 时间和 $O(\min(n, m))$ 空间内完成。 ### 适用前提 1. **最优子结构**：到 $(i,j)$ 的最优路径包含到其前驱的最优路径 2. **无环性**：图中没有环。如果存在正向权重环，则不存在"最长路径"（可以无限绕环增加权重） 3. **有向性**：边有明确的方向，不允许回头 <NoteCard variant="pitfalls" items={[ '动态规划就是填表：', '填表只是实现手段。动态规划的核心是最优子结构、重叠子问题、无后效性三要素。盲目填表而不验证这三个前提，可能导致错误结果。', '所有递归问题都能用动态规划优化：', '只有存在重叠子问题时，动态规划才有优势。例如归并排序的递归子问题相互独立（不重叠），此时分治比 DP 更自然。', 'DP 表的值就是最优解：', 'DP 表存储的通常只是最优值（如最长路径权重），而非最优解本身。要恢复具体路径，需要在填表时记录决策方向（回溯指针），再通过回溯重建。空间受限时需要特殊技巧（如 Hirschberg 算法）。', '混淆路径权重与路径长度：', '曼哈顿游客问题求的是权重之和最大的路径，而非经过边数最少的路径（后者是 BFS 的标准问题）。' ]} /> <LinkGrid items={[ { title: 'Needleman-Wunsch 全局比对', to: '/core-methods/alignment/needleman-wunsch', description: '全局比对的经典 DP 算法，直接源自曼哈顿游客问题。' }, { title: 'Smith-Waterman 局部比对', to: '/core-methods/alignment/smith-waterman', description: '在 DP 框架下寻找最优局部相似区域。' }, { title: '编辑距离', to: '/core-methods/alignment/edit-distance', description: '编辑距离是 DP 的另一个经典应用，与序列比对紧密相关。' }, { title: 'DAG 最长路径', to: '/core-methods/algorithms/dag-longest-path', description: '从曼哈顿网格推广到通用 DAG 的最长路径问题。' }, { title: '仿射 Gap 罚分', to: '/core-methods/alignment/affine-gap-penalty', description: '对基础 DP 比对的扩展，引入更合理的Gap 罚分模型。' }, { title: '分治算法基础', to: '/core-methods/algorithms/divide-and-conquer', description: 'Hirschberg 算法展示了分治如何优化 DP 的空间复杂度。' }, { title: '贪心算法', to: '/core-methods/algorithms/greedy-algorithms', description: '对比贪心与 DP 的优劣。' }, ]} />