Vince Jiang

CSCI3160 / 辅导 · 本站更新

CSCI3160 T06 DP方案恢复与空间

课程：CSCI3160 Design and Analysis of Algorithms 本讲：T06 DP方案恢复与空间 · 原件 T06-动态规划技巧-未核-隐藏.pdf（本地课件） p.1–18 定位：不仅求最优值，还记录决策，并根据依赖关系判断能否压缩。 承接：L07 钢条切割、L09 LCS

p.1–3：最优值不包含全部方案信息【新】

p.1 标题，p.2 重申保存子问题避免重算、按依赖顺序求解。p.3 钢条价格1,5,8,9，对应最优值1,5,8,10；bestSub(t)记录达到最大值的第一段长度，依次1,2,3,2。

p.4–6：附带保存取得最优的选择

p.4 “piggyback technique”

钢条问题的完整式子是 opt(0)=0opt(0)=0 以及

opt(t)=max⁡1≤k≤t{P[k]+opt(t−k)},bestSub(t)∈arg⁡max⁡1≤k≤t{P[k]+opt(t−k)}. opt(t)=\max_{1\le k\le t}\{P[k]+opt(t-k)\},\qquad bestSub(t)\in\arg\max_{1\le k\le t}\{P[k]+opt(t-k)\}.

p.4 可先求完opt，再对每个t枚举k重新寻找P[k]+opt(t−k)的最大者，共O(n²)；也可在填opt时顺手记录，使常数更小。p.5 要输出切法，p.6 从剩余长度l=n出发，输出bestSub(l)，令l减去这段长度，直到0。原例n4：先取2，剩2；再取2，剩0，收入5+5=10。每次至少减1，因此最多n步。并列最优可固定取最小k，保证结果可复现。

p.7–9：区间递推先检查边界是否定义完整

p.7 给出a≥b时f=0；a<b时加区间和，再枚举a<c<b取f(a,c)+f(c,b)最小。p.8 表格位置(a,b)对应区间，p.9 下三角及对角为0，目标右上角f(1,n)。

p.7 的题面是：给定 n 个整数的数组 A，a,b 都在 1 到 n，求 f(1,n)，要求 O(n³) 时间。原式完整写作

f(a,b)={0,a≥b,∑r=abA[r]+min⁡a<c<b{f(a,c)+f(c,b)},a<b. f(a,b)=\begin{cases} 0,&a\ge b,\\ \displaystyle\sum_{r=a}^{b}A[r]+\min_{a<c<b}\{f(a,c)+f(c,b)\},&a<b. \end{cases}

求和下标改用 r 仅为避免与分割 c 混淆，并未改动数学含义。表格用 a 作行、b 作列，例如 p.8 的 f(5,8) 在第5行第8列；每个 a≥b 的位置为0。

这里原公式有缺口：b=a+1时可选c为空，min空集未定义；p.11虽说这些格不依赖其他格，却未补它们的数值。不能直接把“无依赖”推为0。以下讨论依赖顺序与复杂度仍成立；若要实际数值，必须先约定相邻区间边界。

p.10–12：按区间长度推进

图（p.10）：f(4,10)来自同行较左f(4,c)、同列较下f(c,10)。元素：两类区间都比目标短。看什么：行优先从左到右不一定已算下方依赖，按b−a递增最直接。

p.11 第一条上对角线为相邻区间，应先给基值；p.12 间距2的格仅依赖两个间距1格。补充／显式演示约定：取f(a,a+1)=A[a]+A[a+1]，相当于空分割的附加成本设0；这是为补齐示例的假设，不是原件已写条件。数字是我为演示取的，讲义没给：A=(1,2,3)，则f12=3、f23=5、f13=(1+2+3)+3+5=14。

p.13–14：状态数乘每状态工作

p.13 间距3的格依赖较短两种间距，可以在前两条对角线之后计算；p.14 总结每个间距k的格O(k)时间，共O(n²)格，总O(n³)，空间O(n²)。区间和可用前缀和O(1)查询，避免每次候选分割重复求和；即使每状态只求一次区间和O(k)，仍不改变O(n³)。若边界未确定，只能得到结构算法，不能称已经求出原公式唯一数值。

p.10 目标 f(4,10) 具体枚举 c=5,6,7,8,9，分别读取 (f(4,5),f(5,10))、(f(4,6),f(6,10))、(f(4,7),f(7,10))、(f(4,8),f(8,10))、(f(4,9),f(9,10))。p.11 灰格间距1；p.12 绿格间距2，只有一种分割，读两个灰格；p.13 红格间距3，两种分割分别读“灰+绿”和“绿+灰”。颜色表示已完成的依赖层，不是数值大小。

给定相邻区间基值以后，程序先写所有对角和下三角0，再写相邻区间；然后 gap 从2到n−1，a 从1到n−gap，b=a+gap，枚举所有内部分割 c。每轮读取的两区间间距都小于 gap，因此一定已有值。复杂度还可精确按 ∑k=1n−1(n−k)O(k)=O(n3)\sum_{k=1}^{n-1}(n-k)O(k)=O(n^3) 核算。

p.15–17：只保留仍会读取的行

图（p.15–16）：x=ABC、y=BDCA的LCS依赖图。元素：每格只来自左、上或左上；箭头从依赖指向待算格。看什么：计算第i行时只需第i−1行及本行已有前缀，再早的行不会被读取。

实际逐行值（含第0列）：初始0,0,0,0,0；A行为0,0,0,0,1；B行为0,1,1,1,1；C行为0,1,1,2,2。旧行可在算完新行后丢弃，最终长度2。p.17 换行列方向，可令较短字符串为列，额外表空间O(min(n,m))，加保存输入的O(n+m)总空间仍O(n+m)。这只直接保留最优值；若需完整LCS，不能假设已丢掉的父指针还在。

补充：一行 LCS 的变量账本。 每算一行先令 diag=0。第 j 列开始时，row[j] 是上一行同列，row[j-1] 是本行左格，diag 是上一行左格。先 old=row[j]；字符相同则写 diag+1，否则写 max(row[j],row[j-1])；最后 diag=old。执行顺序保证下一列还能读到尚未覆盖前的左上值。

用原例算 C 行第3列：此前数组前缀已成 0,1,1，旧第3列为1，diag=1，对应 C=C，写2；接着把旧值1交给下一列的diag。第4列 C≠A，比较旧上1与新左2，写2。最终行 0,1,1,2,2，与完整表相同。

自测：保留最后一行，能按普通回溯直接找回全部匹配位置吗？

不能。比如要走到上一行某个中间状态，其值和决策已经不在内存。可另存决策，或使用额外的分治重算方法，但必须重新给出空间时间分析；只求长度的空间压缩不是免费保留全部方案信息。

p.18：不是所有 DP 都能两格滚动

p.18 “Can this trick be used to reduce the space in Problem 2?”

钢条opt(t)要看opt(0)至opt(t−1)所有以前值，不能像Fibonacci只留最后两个。原本opt与bestSub都是O(n)，恢复切法也需保留每个可能剩余长度的选择。空间优化来自依赖范围，而不是“DP都能滚动”的口号。

本讲核心考点

  • （C 级 通识）bestSub的含义与恢复循环。
  • （C 级 通识）区间长度决定填表顺序，空候选范围必须单独定义。
  • （C 级 通识）滚动空间只丢弃未来不会读的状态。

附录

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

来源与证据

  • 本次逐页复核：2026-10-13，依据上述本地课件；保留已发布深化内容，页码指 PDF 物理页。历史考试演练保留其原有出处，本次不将旧记录冒充重新阅卷。

  • 原件：T06-动态规划技巧-未核-隐藏.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：无

  • 缺题干解答卷仅用于核对已取得的题面，不由答案反推题目。