2 DP

论文 2.2 节标题是 Dynamic Programming（动态规划）。这一节不是专门讲某个基因组算法，而是用经典的 最长公共子序列（LCS） 作为例子，说明：

• 动态规划的基本思想；
• DP 表是怎么构造的；
• 每个格子依赖哪些邻居；
• 如何从表中得到最终结果；
• 为什么这种计算模式适合后面 GenDP 做硬件加速。

---

1. 动态规划到底在做什么？

Dynamic programming simplifies a complicated problem by breaking it down into sub-problems which can be solved recursively.

动态规划的核心思想是：

把一个大问题拆成若干个子问题，先求解子问题，再把子问题的结果组合起来得到大问题的解。

论文里提到 Bellman 方程，就是用来描述这种“当前状态如何由之前状态递推得到”的公式。

如果子问题会被重复计算，就可以用一个表把结果存起来，避免重复算。这个表就是 DP 表。

所以 DP 通常包含三件事：

1. 定义状态：比如 $c[i,j]$ 表示什么；
2. 写出递推关系：当前状态由哪些更小状态得到；
3. 填表并回溯：按顺序填表，最后找到答案。

---

2. 用最长公共子序列 LCS 来理解

论文定义了两个序列：

$$X_m = \{x_0, x_1, \ldots, x_{m-1}\}$$ $$Y_n = \{y_0, y_1, \ldots, y_{n-1}\}$$

目标是找它们的最长公共子序列。注意，子序列不要求连续，只要求保持原来的先后顺序。

例如：

• $X = A B D$
• $Y = E A B D$

它们的 LCS 是 $A B D$，长度为 3。

论文定义：$\boldsymbol{c[i,j]}$ 表示序列 $\boldsymbol{X_i}$ 和 $\boldsymbol{Y_j}$ 的最长公共子序列长度。

其中 $X_i$ 表示 $X$ 的前 $i$ 个字符，$Y_j$ 表示 $Y$ 的前 $j$ 个字符。

---

3. 递推公式逐条解释

论文给出的公式是：

$$c[i,j] = \begin{cases} 0 & \text{if } i = 0 \text{ or } j = 0 \\ c[i-1,j-1] + 1 & \text{if } i,j > 0 \text{ and } x_{i-1} = y_{j-1} \\ \max(c[i,j-1], c[i-1,j]) & \text{if } i,j > 0 \text{ and } x_{i-1} \neq y_{j-1} \end{cases}$$

可以分三种情况理解。

情况一：$i=0$ 或 $j=0$

如果其中一个序列是空的，那么公共子序列长度当然是 0。

所以：

$c[0,j] = 0$

$c[i,0] = 0$

这就是 DP 表的初始条件。

---

情况二：当前字符相同

如果：

$x_{i-1} = y_{j-1}$

说明 $X$ 的第 $i$ 个字符和 $Y$ 的第 $j$ 个字符相同。

那么它们可以接在之前的最长公共子序列后面，所以：

$c[i,j] = c[i-1,j-1] + 1$

这里用的是 $x_{i-1}$ 和 $y_{j-1}$，是因为数组下标从 0 开始，第 $i$ 个字符对应下标 $i-1$。

---

情况三：当前字符不同

如果：

$x_{i-1} \neq y_{j-1}$

那么这两个字符不能同时作为公共子序列的末尾。

此时有两种选择：

1. 忽略 $X$ 的当前字符，看 $c[i-1,j]$；
2. 忽略 $Y$ 的当前字符，看 $c[i,j-1]$。

取两者中较大的：

$c[i,j] = \max(c[i,j-1], c[i-1,j])$

---

4. DP 表是怎么填的？

论文说，可以根据序列 $X_m$ 和 $Y_n$ 构造一个 DP 表。

表中每个格子 $c[i,j]$ 依赖三个邻居：

• 上边：$c[i-1,j]$
• 左边：$c[i,j-1]$
• 左上对角：$c[i-1,j-1]$

可以画成：

        j-1   j
i-1     ↖    ↑
i       ←   c[i,j]

也就是说：

• 如果字符相同，看左上角；
• 如果字符不同，看上边和左边，取最大值。

第一行和第一列全部填 0。

然后从左到右、从上到下填表。因为每个格子依赖的格子都已经提前算好了。

---

5. 最后结果在哪里？

填完整个表后，表中最大的值就是最长公共子序列的长度。

对于标准 LCS，通常就是右下角：

$c[m,n]$

但论文说“表中最大的值”，这是更一般的说法。

---

6. 什么是 trace back？

得到长度还不够，还要找出具体的公共子序列。这就要做 回溯（trace back）。

从最终格子开始往回走：

• 如果当前字符相同，就走向左上角，并记录这个字符；
• 如果不同，就走向左边或上边中值较大的那个方向。

这样反向走回起点，就能得到具体的 LCS。

论文 Figure 1 中的橙色块链，就是回溯路径。

---

7. 这一节和 GenDP 有什么关系？

2.2 节其实是在为后面做铺垫。

它告诉我们，很多 DP 算法都有类似特征：

• 有一个 DP 表；
• 每个格子依赖相邻格子；
• 可以按波前方式并行计算；
• 有初始化、递推、填表、回溯几个阶段。

后面的基因组 DP kernel，比如：

• BSW：2D DP 表；
• PairHMM：2D DP 表；
• POA：带图结构的长距离依赖；
• Chain：1D DP 表；

它们都可以看成这种“DP 表计算”的变体。

GenDP 的加速思路，就是用 systolic array、PE 阵列、可编程计算单元等，去高效支持这些不同依赖模式、不同目标函数、不同精度的 DP 计算。

---

一句话总结

2.2 节用 LCS 讲清了动态规划的本质：

定义状态 $c[i,j]$，写出递推公式，初始化边界，按依赖关系填表，最后通过回溯得到具体结果。

理解了这个例子，后面看 BSW、PairHMM、POA、Chain 这些基因组 DP kernel 时，就更容易明白它们为什么适合用 GenDP 这类专用加速器来加速。