CSCI3160 L08 动态规划依赖与填表顺序

课程：CSCI3160 Design and Analysis of Algorithms 本讲：L08 动态规划依赖与填表顺序 · 原件 L08-DP-03-Dependency-未核-隐藏.pdf（本地课件） p.1–9 定位：把二维递推画成依赖图，判断行优先、列优先为何都合法，再把整张表算完。承接：#L06-02 动态规划顺序与保存输出

p.1 标题页。

先知道每个状态要读谁（p.2–3）【延伸 L06 p.7–8】

p.2 To figure out a working order, we need to look at the subproblems’ dependency.

p.2 承接 #L06-02：动态规划必须先算依赖项，但多维状态没有天然唯一顺序。合法顺序由递推式决定，不能凭数组长得像表格就任选扫描方向。

p.3 先定义字符串是字符序列；长度为 $\ell$ 的串可以放在长度为 $\ell$ 的数组中，s[i] 表示其第 i 个字符。然后定义字符串与连续子串：若 s=ABCD，s[2]=B，s[2:4]=BCD。下标从 1 开始，区间两端都含。这里的 substring 是连续片段，与下一讲允许跳字的 subsequence 不同。

二维递推的三个分支（p.4–5）【新】

题面（L08-DP-03-Dependency-未核-隐藏.pdf · Problem · p.4）

p.4 x = a string of length n y = a string of length m Consider function f(i,j) defined for any $i\in[0,n]$ and $j\in[0,m]$ : Goal: Compute f(n,m). Example: Let x = ABC and y = BDCA.

公式按讲义重排：

f(i,j)=\begin{cases} 0&i=0\text{ or }j=0,\\ f(i-1,j-1)+1&i,j>0\text{ and }x[i]=y[j],\\ \max\{f(i,j-1),f(i-1,j)\}&i,j>0\text{ and }x[i]\ne y[j]. \end{cases}

p.4 先把函数本身当问题，下一讲才说明它为何表示 LCS。 $i,j$ 分别取 x、y 的前缀长度，0 表示空前缀。p.5 给出依赖定义：算 A 必须知道 B 的输出，则 A 依赖 B。当前字符相同读左上；不相同读左与上，而不是把三个邻居无条件都加起来。

依赖箭头指向后算的格子（p.6）

图（p.6）：x=ABC、y=BDCA 的依赖网格。元素：行号 0–3，列号 0–4；相同字符处从左上格指向当前格，不同字符处从左格及上格指向当前格。看什么：箭头表达计算顺序，即前提指向依赖它的结果。例如 (3,3) 指向 (3,4)，不是要求先算 (3,4)。

算一遍：f(3,3) 对应 C 与 C，读 f(2,2)=1 后加 1，得到 2；f(3,4) 对应 C 与 A，读 f(3,3)=2 和 f(2,4)=1，取 max 得 2。若先填最后一格，就还拿不到这两个输入。

拓扑顺序不唯一（p.7–8）【新】

p.7 if subproblem A depends on subproblem B, then A must appear after B in the ordering.

p.7 的拓扑顺序（topological order）只要求所有前提都先出现，不要求某个唯一排列。p.8 行优先时，上方格子在上一行已算，左方格子在本行较早已算；列优先时，左格在上一列已算，上格在本列较早已算，因此两者都合法。

表（按 p.4 递推算出的完整结果；讲义 p.8 原图为空表）：

x前缀末字／y前缀末字	B	D	C	A
空	0	0	0	0
A	0	0	0	1
B	1	1	1	1
C	1	1	2	2

第一行 A 只有遇到最后的 A 才从 0 增到 1；第二行 B 在第一列匹配，之后把已有的 1 向右传；第三行 C 在第三列匹配，把左上 1 增到 2，最后保留 2。每一格都有已完成前提，最终 f(3,4)=2。

补充：用一条严格下降的量检查是否有循环依赖。 本讲 f(i,j) 只读取下标和更小的状态：左与上使 i+j 减 1，左上使它减 2。因此沿依赖不断向前追，不可能回到同一个状态。按 i+j 从小到大逐条反对角线计算也是合法的；同一反对角线内部互不依赖。

若把列从右向左扫，即使上一行已完成，f(3,4) 所需的同一行 f(3,3) 仍未算好。这是明确的失败见证，不是只说“逆序不合适”。不过不存在“所有 DP 都必须正序”的法则：若另一递推依赖右边或更长后缀，就应相应反向。

自测：把表压成一行，左上旧值会在哪里丢失？

正向更新第 j 格之前，数组第 j 格还是上一行，j−1 格却已经变成本行；因此左上角的旧 j−1 值已被覆盖。需用一个临时变量保存它：先记下旧第 j 格，再计算新第 j 格，随后把所记旧值交给下一列作为左上角。只“删掉一维”而不跟踪新旧版本，会改变递推读到的含义。

由 p.8 的行优先顺序展开算法：

创建 F[0..n,0..m]
把第 0 行和第 0 列置为 0
for i 从 1 到 n：
  for j 从 1 到 m：
    若 x[i] = y[j]：F[i,j] = F[i-1,j-1] + 1
    否则：F[i,j] = max(F[i,j-1], F[i-1,j])
返回 F[n,m]

列优先版本只把两个循环的内外交换，仍让各自下标递增。按原页列出的顺序，完整行优先起始为 (0,0),(0,1),…,(0,4),(1,0),…,(1,4)；列优先起始为 (0,0),(1,0),…,(3,0),(0,1),…,(3,1)。预先统一置零边界与这样逐个处理边界得到同一值表。

时间等于状态数乘每格工作（p.9）

p.9 For any f(i,j), we can compute it in O(1) time, given the outputs of the subproblems it depends on.

已有依赖结果后，每格只做字符比较、一次加法或一次 max，代价常数；状态数 $(n+1)(m+1)$ ，正长度下总时间 $O(nm)$ ，完整表空间同阶。实例有 4×5=20 个含边界状态，12 个内部状态。二维数组本身不保证二次时间：如果某格还要枚举 k 个选择，必须把枚举成本乘进去。

考试角度：（C 级通识）常见考法是给出一个扫描顺序，让你找出某格所依赖但尚未计算的具体格子，而不是只回答“顺序不对”。

补充对应的往年题演练见附录 A1。

本讲核心考点

依赖由递推式决定，箭头表示先算到后算（p.5–6，C 级）。
行优先与列优先均满足本递推的拓扑要求（p.7–8，C 级）。
每格O(1)、共O(nm)格，才能推出O(nm)时间（p.9，C 级）。

附录

本讲所需过程已在正文展开。

A1 作业/往年题演练（非讲义内容）：离散 Fréchet 距离

题面（Final-2025T1-题目.pdf · Q9 · p.3–4；扫描件，视觉读取；公式按原题重排）

p.3 “9. (10 points) (Discrete Fréchet Distance.) Consider Professor Bille going for a walk with his personal dog. The professor follows a path of points $p_1,\ldots,p_n$ and the dog follows a path of points $q_1,\ldots,q_m$ . We assume that”

p.4 “the walk is partitioned into a number of small steps, where the professor and the dog in each step either both move from $p_i$ to $p_{i+1}$ and from $q_j$ to $q_{j+1}$ , respectively, or only one of them moves and the other stays.”

“Please design an efficient algorithm to find the smallest possible length L of the leash, such that the professor and the dog can move from $p_1$ and $q_1$ , respectively, to $p_n$ and $q_m$ . They cannot move backwards, and we only consider the distance between points. The distance L is also known as the discrete Fréchet distance. Please also justify why your algorithm is efficient. [Hint: Dynamic programming.]”

“To help you better understand this question, we've included an example in Figure 2. In this example, the dotted lines denote where Professor Bille (black nodes) and the dog (white nodes) are at time 1 to 8. The minimum leash length is the distance between $p_1$ and $q_4$ .”

图（题面，p.4）：上方五个黑点p1至p5，下方七个白点q1至q7。元素：虚线依次连接(p1,q1)、(p1,q2)、(p1,q3)、(p1,q4)、(p2,q5)、(p3,q6)、(p4,q7)、(p5,q7)。看什么：停留允许，回退禁止，目标限制的是所有阶段最大距离。图没给坐标，不能从截图量出数值距离。

设 d(i,j) 是输入点 pi、qj 的距离，D(i,j) 是从起点走到这一对位置所需的最小绳长。最后一步只能从(i−1,j)、(i,j−1)、(i−1,j−1)三者来。沿任何一种走法，绳长既要覆盖前面全程，又要覆盖当前距离，所以

D(i,j)=\max\left(d(i,j),\min\{D(i-1,j),D(i,j-1),D(i-1,j-1)\}\right).

边界 D(1,1)=d(1,1)；第一行 D(1,j)=max(D(1,j−1),d(1,j))，第一列同样累积最大值。按行或按i+j递增填表，全部依赖先算好。为什么先min再max成立？函数max(d,x)随x单调不减，在三种前驱中选最小的历史所需绳长，不会被当前距离罚得更坏；三种又穷尽最后一步，所以不漏最优路径。每格常数工作，共nm格，时间O(nm)、保存全表空间O(nm)，答案D(n,m)。只求长度可滚动为O(m)，恢复走法则另存前驱。

补充核算（数字是我为演示取的，讲义没给）：一维点P=(0,2)、Q=(0,1,2)。距离表两行为(0,1,2)、(2,1,0)。DP第一行(0,1,2)，第二行第一格2，第二格max(1,min(1,2,0))=1，第三格max(0,min(2,1,1))=1。最终绳长1，可走(0,0)→(2,1)→(2,2)，逐步距离0、1、0。长度不可能0，因为必须访问Q中的1，而P只有0或2。

回到正文：本讲正文

来源与证据

本次逐页复核：2026-10-13，依据上述本地课件；保留已发布深化内容，页码指 PDF 物理页。历史考试演练保留其原有出处，本次不将旧记录冒充重新阅卷。
原件：L08-DP-03-Dependency-未核-隐藏.pdf（本地课件）；页码均为 PDF 页号。
版本记录（2026-09-17）：当时从教师官网下载并逐字节核对，与本地原件一致；此日期不是本次重新联网核验。原始学期未核，不据网页学期补猜。
发布状态（2026-09-17 核验时）：官网链接所在行隐藏，当时按预习参考处理；不据此推断后续发布或考试范围。
既有考试证据记录（2026-09-17）：当时读取了教师官网、Midterm-2021T1-题目.pdf、Midterm-2021T1-题解.pdf、Review-Quiz-2020T2-题目.pdf、Review-Quiz-2020T2-题解.pdf、Quiz-01-2025T1-题解.pdf、Midterm-A-2025T1-缺题干-解答.pdf、Quiz-02-2025T1-缺题干-解答.pdf、Quiz-03-2025T1-缺题干-解答.pdf、Final-2021T1-题解.pdf、Final-2024T1-缺判断-题目.pdf、Final-2025T1-题目.pdf、Final-2025T1-缺题干-解答.pdf；未识别用途的 PDF：无
缺题干解答卷仅用于核对已取得的题面，不由答案反推题目。