CSCI3160 Regular 6：DP 依赖、空间与方案恢复

原件：题目（本地课件） p.1–2；官方答案（本地课件） p.1–3。定位：把重复递归变成有序求值，并区分“算出最优值”和“恢复实际方案”。

题意为中文概述；下文含本解析补充的推导及例子。Q3 原公式缺少相邻区间的边界，已对 PDF 图像核对，不能静默替老师补定义。

Problem 1：为什么直接递归是指数时间

题目对每个正整数 x 枚举 i=1,…,x，并递归计算 f(x−i)，没有缓存。最大值最终取哪一个不影响时间：所有分支都先算完。

令 C(x) 为一次 f(x) 执行产生的总函数调用数，包含自身，则

C(0)=1,\qquad C(x)=1+\sum_{j=0}^{x-1}C(j).

对 x≥1，将相邻两式相减得 $C(x)=2C(x-1)$ ，故 $C(x)=2^x$ 。每次调用至少做常数工作，计算 f(n) 至少花 $\Omega(2^n)$ 。这里不是“分支看起来很多”，而是精确统计调用树。

自取 n=3：f(3) 调 f(2)、f(1)、f(0)；f(2) 再调 f(1)、f(0)；两个 f(1) 又分别调 f(0)。总调用数为 8，而不同状态只有 0、1、2、3 四个。DP 的优化正是每个不同状态只算一次，而非改变数学递推式。

Problem 2：切钢条时顺便记下最优第一段

对长度 t，枚举第一段长度 i，候选收入为 $P[i]+opt[t-i]$ 。按 t 从小到大填表，因为 t−i<t，依赖值已经得到。更新最优值时同时保存 i：

opt[0] ← 0
对 t=1,…,n：
    opt[t] ← 负无穷
    对 i=1,…,t：
        若 P[i]+opt[t-i] > opt[t]：
            opt[t] ← P[i]+opt[t-i]
            bestSub[t] ← i

一共比较 $1+2+\cdots+n=n(n+1)/2$ 次，时间 $O(n^2)$ ，两个数组空间 $O(n)$ 。负无穷初始化允许价格为负时仍要求处理完整长度；平局任选一个即可得到某个最优方案。

恢复时令 t=n，输出 bestSub[t]，再减去它，直到 t=0。每次输出的段至少长 1，因此至多 n 次。正确性来自每一步保存的等式 $opt[t]=P[i]+opt[t-i]$ ：沿这些等式展开，所有段收入之和恰是 opt[n]，所有长度之和恰是 n。

自取价格 [2,6,7,9,10]：opt[0..5] 为 [0,2,6,8,12,14]。采用最早严格改进的平局规则，bestSub[5]=1、bestSub[4]=2、bestSub[2]=2，因此恢复段长 1、2、2，总收入 2+6+6=14。不能在恢复时一直查询 bestSub[n]；剩余长度已经改变。

Problem 3：区间 DP 与原题遗漏的边界

原题给出 a≥b 时 f(a,b)=0，否则为区间元素和加上内部切点 c 的最小值，切点范围 a+1,…,b−1，左右子问题为 f(a,c)、f(c,b)。

按原式，f(a,a+1) 的最小化集合为空。 实数范围内“空集合的最小值”不存在，所以原题没有定义完整的有限函数，不能声称已算出唯一数值答案。若采用优化中 $\min\varnothing=+\infty$ 的扩展约定，所有 a<b 的值都变成正无穷；这并不是通常想考的有限区间 DP。

在补充任意明确的相邻边界 B[a]=f(a,a+1) 后，所需三次方算法如下。B 的取值须由题目补充，不在此冒充官方定义。

设置 f[a,a]=0，f[a,a+1]=B[a]
计算前缀和 H[0]=0，H[t]=H[t-1]+A[t]
对 gap=2,…,n-1：
    对 a=1,…,n-gap：
        b ← a+gap
        best ← 正无穷
        对 c=a+1,…,b-1：
            best ← min(best, f[a,c]+f[c,b])
        f[a,b] ← H[b]-H[a-1]+best

为什么按 gap？两个依赖区间的跨度 c−a、b−c 都严格小于 b−a，因此已计算。前缀和把区间求和降到常数，但即使每状态线性求和，总体仍为三次方；关键不能让子问题反复递归计算。状态数 $O(n^2)$ ，每状态至多 n 个切点，时间 $O(n^3)$ 、空间 $O(n^2)$ 。

补充演算，仅展示条件算法。 若自行约定相邻边界均为 0，A=[1,2,3] 时 f(1,3)=6+f(1,2)+f(2,3)=6。若改为 B[1]=10、B[2]=20，则结果变为 36。两个数不同，具体说明为什么不能忽略边界缺失。官方答案 p.2 说明了按跨度求值，但未补上此边界。

Problem 4：LCS 长度的滚动数组

题目引用的 L08（本地课件） p.4、p.9 是 LCS 长度递推：字符相同时取左上加一，不同时取上、左最大，首行首列为零。

求第 i 行时，只需上一行的 j 和 j−1，以及本行已算完的 j−1，所以保留 prev、cur 两行即可：

prev[0..m] ← 0
对 i=1,…,n：
    cur[0] ← 0
    对 j=1,…,m：
        若 x[i]=y[j]：cur[j] ← prev[j-1]+1
        否则：cur[j] ← max(prev[j],cur[j-1])
    交换 prev、cur
返回 prev[m]

交换后 prev 才是最新行，不能错返回已经作为缓冲区的旧行。辅助空间 O(m)，输入两个串还需 O(n+m)，总空间满足 O(n+m)。将较短串作列可把辅助空间缩到 O(min(n,m))；时间仍 O(nm)。

原讲义 x=ABC、y=BDCA：四行从空串开始依次为 [0,0,0,0,0]、[0,0,0,0,1]、[0,1,1,1,1]、[0,1,1,2,2]，最后结果 2。只求长度可以丢旧行；直接恢复路径不能再假装整张表仍在。

Problem 5：DAG 上依赖入邻居的最小值

无入边顶点 f=0；其余顶点 $f(u)=1+\min_{v\in IN(u)}f(v)$ 。它表示从某个源点到 u 的最短边数，而非任意指定源点的距离。

先求拓扑序，再顺序处理顶点。构建入邻接表后，每个顶点一次扫描自己的入边，就能得到最小前驱值；所有入边合计 m 条，连同拓扑排序，总时间 O(n+m)。也可初始化所有源点为 0，其他为无穷，沿拓扑序用出边传播 min。

自取图 s→a、s→b、a→c、b→d、d→c：拓扑序 s,a,b,d,c。f 分别为 0、1、1、2、2，c 经 a 只需两条边，不能被另一条三边路径覆盖成 3。归纳证明：处理 u 时前驱都正确，任何到 u 的非空路径有最后一条前驱边；取最小枚举了所有可能。

补充：同样一个 DAG，换输出语义就要换初始化。 Q5 问“从任意源点出发”的最短边数，所以每个入度0顶点均为0。若改成只从指定s出发，就必须令s=0、其他点无穷；否则会把从另一源点开始的短路误记成s到该点的距离。自取两条边 s→a、t→b，指定s时b不可达；多源题里b却为1。状态定义决定基值，不能只背“源点都填0”。

自测：为什么依赖入邻居时用拓扑正序，而可达最小权值题用逆序？

前者的结果由走进当前点的最后一条边决定，前驱须先算；后者由从当前点走出去的第一条边决定，后继须先算。看递推箭头方向再选顺序，图本身是DAG还不足以决定正序还是逆序。

Problem 6：DAG 最长路径

把 Q5 的 min 换成 max，得到以 u 为终点的最长路径边数 L(u)；源点仍为 0。DAG 不会允许重复绕环，因此最长路径有限，且拓扑顺序能安全计算。

L(u)=\begin{cases}0&IN(u)=\varnothing,\\1+\max_{v\in IN(u)}L(v)&\text{otherwise}.\end{cases}

答案为所有顶点 L(u) 的最大值，不是随意选最后一个顶点的值。保存取得最大值的前驱可恢复路径，回溯后反转；处理每条边一次，总时间 O(n+m)。上述例子中 L(c)=3，路径 s,b,d,c；Q5 的最短值为 2，二者不可混淆。孤立点路径长度为 0，因为本题数边而不是数顶点。

来源与证据

官方题目 p.1–2、答案 p.1–3；Q4 另核对 L08 p.4–9。Q3 为条件不完整题，已明确区分原式与补充边界后的算法。本文不据练习推断考试范围。