Part 1: 分治法

🔹 1. 主定理 (Master Theorem)

【识别信号】

  • 题干给出递归式 T(n) = aT(n/b) + f(n)，要求给出渐近界 Θ(·) 或 O(·)。
  • 关键词：solve recurrence, asymptotic bound, divide and conquer runtime。
  • ⚠️ 失效信号：若递归式为 T(n-1)、T(n/2 + 1)、a<1、或 f(n) 非多项式/震荡（如 2^n, n log n 但差距非多项式级），主定理直接失效，必须改用递归树或迭代展开。

【直觉类比】
“分家产比大小”。n^{log_b a} 是递归树最底层所有叶子的总工作量（分下去的代价），f(n) 是每一层划分+合并的工作量（合起来的代价）。谁在数量级上碾压对方，谁就主导整棵树的总耗时。如果两者旗鼓相当，则每层代价累加，多出一个 log n 因子。

【数学骨架】

  • 临界指数：c = log_b a （叶子层的增长阶）
  • Case 1（叶子主导）：若 f(n) = O(n^{c-ε})（ε>0 为任意小常数） → T(n) = Θ(n^c)
    (释义：合并代价比叶子代价多项式级地小，总时间被底层递归调用数量统治)
  • Case 2（层层平衡）：若 f(n) = Θ(n^c log^k n)（k≥0） → T(n) = Θ(n^c log^{k+1} n)
    (释义：每层代价同阶，共 log_b n 层，总时间 = 单层代价 × 层数。注意 log 指数要 +1！)
  • Case 3（根主导）：若 f(n) = Ω(n^{c+ε}) 且满足正则条件 a·f(n/b) ≤ d·f(n)（d<1） → T(n) = Θ(f(n))
    (释义：合并代价多项式级地大，且子问题代价衰减足够快，总时间被顶层/根节点统治)

【证明模板】

  • 白话逻辑：画递归树。第 i 层有 a^i 个节点，每个规模 n/b^i，该层总代价为 a^i · f(n/b^i)。将所有层代价求和。Case 1 是几何递减级数（首项/叶子最大）；Case 2 是每层相等（层数乘单层）；Case 3 是几何递增级数（末项/根最大）。正则条件保证 Case 3 的子问题代价不会反弹。
  • 数学符号：T(n) = Σ_{i=0}^{log_b n} a^i f(n/b^i)。比较 f(n) 与 n^{log_b a} 的阶，利用等比数列求和性质得主导项。
  • 考场直接抄写骨架：
    1
    2
    3
    4
    5
    6
    由递归树展开，第 i 层代价为 a^i f(n/b^i)，共 log_b n 层。
    计算临界值 c = log_b a。比较 f(n) 与 n^c：
    - 若 f(n) 多项式小于 n^c，属 Case 1，T(n)=Θ(n^c)
    - 若 f(n) = Θ(n^c log^k n)，属 Case 2，T(n)=Θ(n^c log^{k+1} n)
    - 若 f(n) 多项式大于 n^c 且满足正则条件，属 Case 3，T(n)=Θ(f(n))
    代入本题参数得 T(n)=Θ(...)。

【复杂度直觉】

  • 正向速算：a=2,b=2,f=n → c=1 → Case2 → O(n log n)；a=3,b=2,f=n → c≈1.58>1 → Case1 → O(n^1.58)；a=2,b=4,f=n^{2/3} → c=0.5<0.66 → Case3 → O(n^{2/3})。
  • 逆向反推：题干暗示 O(n log n) 且是分治 → 必为 a=b, f(n)=Θ(n)。若给 O(n^2) → 可能是 a=4,b=2 或 f(n)=Θ(n^2)。若题目故意给 T(n)=2T(n/2)+n/log n → 差距非多项式，主定理失效，需用递归树得 O(n log log n)。
  • 考场避坑：log^k n 的 k 必须写对；Case 3 必须提一句“满足正则条件”；遇到 T(n-1) 直接写“主定理不适用，改用迭代法”。

🔹 2. 归并排序与逆序对计数 (Merge Sort & Inversions)

【识别信号】

  • “排序”、“统计不一致对/逆序对数量”、“O(n log n) 找满足 i<j 且 A[i]>A[j] 的对数”、“两个排列的差异度”。
  • 真题映射：Final Q1（QS vs US News 排名不一致对数）。

【直觉类比】
“两列已排好队的士兵合并”。逆序对就是“右边的人比左边的人矮，却排在后面”。合并时一旦发现右边当前的人更矮，说明他比左边剩余的所有人都矮。因为左边已经有序，不需要逐个比，直接批量计数左边还剩几个人。

【数学骨架】

  • 分治框架：Sort(l, r) → mid=⌊(l+r)/2⌋ → 递归 Sort(l, mid) 与 Sort(mid+1, r) → Merge(l, mid, r)
  • 合并计数核心：维护指针 i=l（左半段）, j=mid+1（右半段）。临时数组 Temp。
    • 若 A[i] ≤ A[j]：Temp.push(A[i]), i++
    • 若 A[i] > A[j]：Temp.push(A[j]), j++, 逆序对计数 += (mid - i + 1)
  • (释义：mid-i+1 是左半段当前未合并的元素个数。因左右子数组已递归有序，A[j] < A[i] 必然意味着 A[j] 小于 A[i...mid] 的所有元素。这 mid-i+1 个元素在原数组中索引均小于 j 但值大于 A[j]，故一次性贡献这么多逆序对，不重不漏)
  • 最终答案：递归返回时累加左、右、跨区三部分计数。

【证明模板】

  • 白话逻辑：循环不变量：已合并部分有序，且已统计的逆序对覆盖所有跨左右子数组的配对。当 A[i]>A[j] 时，由有序性，A[j] 与 A[i...mid] 均构成逆序。递归基 n=1 逆序为0。归纳保证全局正确。合并过程遍历所有跨区对，且利用局部有序性在 O(1) 内批量计数。
  • 数学符号：设左半 L 右半 R 已有序。对任意 x∈R，若 x < L[i]，则 ∀k∈[i, mid], x < L[k]。跨区逆序数 = Σ_{x∈R} |{y∈L | y>x}|。合并指针扫描恰好遍历所有 (y,x) 对，计数等价。
  • 考场直接抄写骨架：
    1
    2
    3
    4
    5
    6
    算法：魔改归并排序。递归划分至单元素。合并时维护双指针 i,j。
    若 A[i]≤A[j] 放 A[i]；若 A[i]>A[j] 放 A[j] 并累加 (mid-i+1) 至计数器。
    正确性：因左右子数组已有序，A[i]>A[j] 时 A[j] 必小于左半剩余所有元素。
    这些元素在原序列中索引均小于 j 但值更大，恰构成逆序对。
    合并过程线性扫描覆盖所有跨区配对，不重不漏。递归基 n=1 计数为0。
    由强归纳法，算法正确统计全局逆序对。

【复杂度直觉】

  • 正向：T(n)=2T(n/2)+O(n) → 主定理 Case 2 → O(n log n)。空间 O(n)（临时数组）。
  • 逆向：题干要求“严格快于 O(n²) 统计配对/排名差异/满足某大小关系的对数” → 90% 是魔改归并。必须写出 mid-i+1 批量累加逻辑，逐个比对直接扣一半分。
  • 考场细节：若题目是“两个排列 q 和 u 的不一致对”，先按 q 升序重排，提取 u 序列，再跑逆序对计数。预处理 O(n log n) 不改变总阶。

🔹 3. 最近点对 (Closest Pair in 2D)

【识别信号】

  • “二维平面上 n 个点”、“最小欧氏距离”、“要求 O(n log n)”、“几何分治”。

【直觉类比】
“切蛋糕找最近的两颗芝麻”。先竖切一刀，左右各自找最近距离 d。真正的答案要么在左/右，要么“跨中线”。跨中线的点对必须挤在宽度为 2d 的条带里。把条带里的点按 y 排序后，对于任意点，只需要向下看常数个点（鸽巢原理保证），再远的 y 距离必然超过 d，无需计算。

【数学骨架】

  • 预处理：按 x 坐标排序点集 P_x（仅一次，O(n log n)）。
  • 分治：mid 划分左右，递归得 d_L, d_R，令 d = min(d_L, d_R)。
  • 合并（条带扫描）：
    1. 提取条带 S = {p ∈ P | |p.x - mid.x| < d}。
    2. 将 S 按 y 坐标排序得 S_y。
    3. 遍历 S_y，对每个 p_i，仅检查后续 p_j 满足 p_j.y - p_i.y < d 的点（最多 7~11 个）。
    4. 若 dist(p_i, p_j) < d，更新 d = dist(p_i, p_j)。
  • (释义：条带内点按 y 排序后，若 y 差 ≥ d，欧氏距离必 ≥ d，直接跳过。几何鸽巢证明保证常数个候选，合并阶段降为 O(n)。注意：S_y 的排序必须随递归线性合并维护，绝不能在每层调用 sort()，否则退化 O(n log² n))

【证明模板】

  • 白话逻辑：正确性核心在条带扫描的常数界。将 2d×d 矩形划分为 d/2×d/2 小格，每格最多1点（否则递归已找到更小距离）。故 p_i 周围 d×2d 区域内点数有常数上界（通常证得 ≤7 或 ≤11）。检查超过该数量的点数学上冗余。
  • 数学符号：设 δ = min(d_L, d_R)。跨中线点对 (p,q) 必满足 |p.x - mid.x|<δ 且 |q.x - mid.x|<δ。将条带划分为 δ/2 × δ/2 网格。由递归定义，同侧点距 ≥δ，故每格至多1点。对任意 p_i∈S_y，满足 0 < p_j.y - p_i.y < δ 的 p_j 必落在以 p_i 为底的 δ×2δ 矩形内，该矩形最多覆盖常数个网格，故候选数 O(1)。
  • 考场直接抄写骨架：
    1
    2
    3
    4
    5
    算法：按 x 排序后分治。递归得 d=min(dL,dR)。提取 |x-mid.x|<d 的条带点集 S。
    将 S 按 y 排序。遍历 S，对每个点仅检查后续 y 差 < d 的常数个点，更新 d。
    正确性：跨中线最近点对必落在宽 2d 条带内。将条带划分为 d/2×d/2 网格，
    由递归性质每格至多1点。故任意点周围 d 半径内候选点数为常数。
    合并阶段线性扫描即可覆盖所有可能更优的跨区点对。

【复杂度直觉】

  • 正向：若 y 排序线性合并：T(n)=2T(n/2)+O(n) → O(n log n)。空间 O(n)。
  • 致命陷阱：条带按 y 排序绝不能每次调用 sort()，否则 T(n)=2T(n/2)+O(n log n) → O(n log² n) 直接扣分。必须写“随递归返回线性合并维护 y 有序数组”或“预处理双份数组（Px, Py）同步划分”。
  • 逆向：题干给“二维点集+最小距离+O(n log n)”必考此题。若只要求 O(n²) 暴力即可。若考“最近点对输出具体坐标”，记得在更新 d 时同步记录点对索引。

🔹 4. 线性时间选择 (Median-of-Medians / Deterministic Selection)

【识别信号】

  • “未排序数组找第 k 大/小元素”、“找中位数”、“要求严格 O(n) 最坏情况时间”、“不能用排序”。

【直觉类比】
“找标杆分堆”。随便找个pivot可能极偏（导致 O(n²)）。为了保证每次切分至少扔掉固定比例的元素，我们“分组找中位数，再找中位数的中位数”作为pivot。这个pivot数学上保证至少比 30% 的元素大，也比 30% 的元素小。每次递归规模最多剩 70%，等比衰减保证总时间线性。

【数学骨架】

  • 步骤：
    1. 将数组 A 分为 ⌈n/5⌉ 组，每组 5 个元素。
    2. 找出每组的中位数（插入排序 O(1)），构成集合 M。
    3. 递归调用 Select(M, ⌈|M|/2⌉) 找到中位数的中位数 x（作为pivot）。
    4. 用 x 划分 A 为 L(<x), M(=x), R(>x)。
    5. 若 k ≤ |R| 递归 Select(R, k)；若 k ≤ |R|+|M| 返回 x；否则递归 Select(L, k-|R|-|M|)。
  • (释义：5个一组是数学临界点。一半的组中位数 ≥x，每组至少3个元素 ≥ 该组中位数，故至少 3·(n/10) = 3n/10 个元素 ≥x。同理 ≤x 的元素也 ≥3n/10。故 L 和 R 的规模均 ≤ 7n/10。递归式 T(n) ≤ T(n/5) + T(7n/10) + O(n) 保证线性)

【证明模板】

  • 白话逻辑：pivot x 是“中位数的中位数”。至少一半的组，其中位数 ≥ x。在这些组里，至少有3个元素 ≥ 该组中位数 ≥ x。所以全局至少 3n/10 个元素 ≥ x。同理至少 3n/10 个元素 ≤ x。每次划分后，最坏情况只需递归进入规模 ≤ 7n/10 的子数组。递归树每层工作量几何衰减，总和收敛于 O(n)。
  • 数学符号：设 T(n) 为最坏时间。找组中位数 O(n)，递归找 x 耗时 T(n/5)，划分 O(n)，递归子问题最大规模 7n/10 耗时 T(7n/10)。得 T(n) ≤ T(n/5) + T(7n/10) + cn。代入归纳假设 T(n) ≤ 20cn 验证成立。
  • 考场直接抄写骨架：
    1
    2
    3
    4
    5
    6
    算法：5个一组求中位数得集合M。递归求M的中位数x作pivot。
    按x划分A为L,M,R。根据k所在区间递归或返回x。
    正确性/复杂度：x为中位数的中位数，至少一半组的中位数≥x。
    每组至少3元素≥该组中位数，故全局≥3n/10元素≥x。同理≤x元素≥3n/10。
    划分后子问题规模≤7n/10。递归式 T(n)≤T(n/5)+T(7n/10)+O(n)。
    由代入法/递归树几何衰减，得 T(n)=O(n)。

【复杂度直觉】

  • 正向：T(n) ≤ T(n/5) + T(7n/10) + O(n) → O(n)。空间 O(log n)（递归栈）。
  • 变式反推：若题目问“为什么不用3个一组？” → 答：T(n) ≤ T(n/3) + T(2n/3) + O(n)，系数和 1/3+2/3=1，每层工作量不衰减，总时间 O(n log n)。必须 ≥5 才能保证系数和 <1。
  • 考场细节：若只要求“平均 O(n)”，直接用随机化 Quickselect 即可，无需 Median-of-Medians。题干强调“最坏情况 O(n)”或“deterministic”才用此算法。

🔹 5. 快速傅里叶变换 (FFT)

【识别信号】

  • “多项式乘法”、“信号卷积”、“系数表示转点值表示”、“要求 O(n log n)”、“复数单位根”。

【直觉类比】
“换赛道超车”。系数表示下多项式乘法是卷积，暴力 O(n²)。但如果把多项式变成“点值表示”（代入 n 个不同的 x 算出 y），乘法就变成对应 y 值直接相乘，O(n) 搞定。FFT 的魔法在于：精心挑选 n 次单位根 作为代入点，利用对称性和折半性质，把“求值”和“插值”都加速到 O(n log n)。

【数学骨架】

  • 核心定义：n 次单位根 ω_n^k = e^{i·2πk/n}，k=0..n-1。满足 ω_n^{k+n/2} = -ω_n^k（折半引理）。
  • 分治求值（Cooley-Tukey）：
    多项式 A(x) = A_even(x²) + x·A_odd(x²)。
    代入 ω_n^k：
    • k < n/2: A(ω_n^k) = A_even(ω_{n/2}^k) + ω_n^k · A_odd(ω_{n/2}^k)
    • k ≥ n/2: A(ω_n^k) = A_even(ω_{n/2}^{k-n/2}) - ω_n^{k-n/2} · A_odd(ω_{n/2}^{k-n/2})
  • (释义：将 n 个点值计算拆成两个 n/2 规模的子问题。平方单位根恰好降阶为 n/2 次单位根。正负号对称性让后半段直接复用前半段结果，无需重复计算。递归式 T(n)=2T(n/2)+O(n) → O(n log n))
  • 逆 FFT (IFFT)：将 ω_n 替换为 ω_n^{-1}，跑完全相同算法，最后结果除以 n。
    (释义：点值转系数本质是乘 Vandermonde 矩阵的逆。逆矩阵元素恰为 1/n · ω_n^{-jk}，结构与前向 FFT 完全同构)

【证明模板】

  • 白话逻辑：单位根的平方恰好是低一阶的单位根（折半引理），且前后半段互为相反数（消去引理）。这使得计算 n 个点值时，只需算 n/2 个，另一半直接取负号复用。递归树每层 O(n)，共 log n 层。逆过程矩阵求逆恰好是共轭单位根加缩放，算法结构不变。
  • 数学符号：V_{j,k} = ω_n^{jk}。V^{-1}_{j,k} = (1/n)ω_n^{-jk}。验证 V·V^{-1}=I：对角线 Σ 1/n = 1；非对角线等比数列求和分子 1-ω_n^{n(j-k)}=0。故 IFFT 正确。
  • 考场直接抄写骨架：
    1
    2
    3
    4
    5
    6
    7
    算法：补零至长度 2^m。按奇偶系数拆分 A_even, A_odd。
    递归计算在 n/2 次单位根处的值。利用 ω_n^{k+n/2}=-ω_n^k 合并：
    前半段相加，后半段相减。递归基 n=1 直接返回。
    逆FFT：将 ω_n 换为 ω_n^{-1}，运行相同算法，最终结果除以 n。
    正确性：由单位根折半引理与消去引理，n 点求值降为两个 n/2 子问题。
    合并线性耗时，T(n)=2T(n/2)+O(n)→O(n log n)。
    逆过程对应 Vandermonde 矩阵求逆，结构同构，仅替换共轭根并缩放 1/n。

【复杂度直觉】

  • 正向：T(n)=2T(n/2)+O(n) → O(n log n)。空间 O(n)。
  • 考场陷阱：多项式度数 n-1，乘积度数 2n-2，必须补零至 ≥2n-1 的 2 的幂次长度，否则点值数量不够唯一确定乘积多项式，直接扣逻辑分。
  • 逆向：题干出现“卷积/多项式乘/大整数乘(转多项式)/模式匹配”且要求 O(n log n) → 必考 FFT。若只要求写思路，重点写“奇偶拆分+单位根对称性+折半递归”。不要求背蝴蝶图代码。

Part 2: 动态规划 DP

🔹 1. 线性 DP (LIS / 加权区间调度 / 作业调度)

【识别信号】

  • “最长递增子序列”、“选不重叠区间最大化权重/数量”、“序列决策/前缀最优/以某元素结尾”、“截止时间/处理时间调度”。
  • 真题映射：Assignment 2 LIS、Final Q3 (Job Scheduling max count)、加权区间调度。

【直觉类比】
“搭积木/排班表”。当前决策只依赖“前面某个兼容状态的最优解”。必须强制“以当前元素结尾”或“考虑前 i 个”，否则无法判断后续能否接上。就像排队，你只关心“上一个 compatible 的人是谁”，不关心更早的历史。

【数学骨架】

  • LIS：dp[i] = 以 A[i] 结尾的最长递增子序列长度。
    dp[i] = 1 + max({0} ∪ {dp[j] | j<i, A[j]<A[i]})
    (释义：强制包含 A[i]，枚举所有合法前驱 j，取最长接续。1 代表 A[i] 自身)
  • 加权区间调度：按结束时间排序。p(i) = i 开始前最晚结束的兼容区间索引。
    dp[i] = max(dp[i-1], w_i + dp[p(i)])
    (释义：dp[i-1] 不选 i 继承前序；w_i + dp[p(i)] 选 i，跳到兼容的最近前驱 p(i) 接续，保证不重叠且总权重最大)
  • Final Q3 变式 (带截止时间的最大任务数)：
    dp[i][t] = 前 i 个任务，总处理时间恰好为 t 时，能完成的最大任务数
    dp[i][t] = max(dp[i-1][t], dp[i-1][t-p_i] + 1) （需满足 t ≥ p_i 且 t ≤ d_i）
    (释义：t 是累计耗时。因任务已按 deadline 排序，若选 i，它必是当前选中集合最后一个完成的，完成时间即 t，故只需检查 t≤d_i)

【证明模板】

  • 白话逻辑：最优子结构：若全局最优解包含 i，则 i 之前的部分必是子问题最优（否则可替换得更优）。无后效性：当前决策只依赖前驱状态，不影响未来合法性。枚举/二分查找覆盖所有合法转移，归纳保证 dp[i] 维护全局最优。
  • 数学符号：设 OPT(i) 为前 i 项最优值。对第 i 项仅“选/不选”两决策。若选 i，则前驱必为 OPT(p(i)) 或 OPT(i-1, t-p_i)。由归纳假设子问题最优，故 dp[i] = max(...) 收敛至 OPT(i)。
  • 考场直接抄写骨架：
    1
    2
    3
    4
    5
    6
    状态定义：dp[i] 表示以 i 结尾/考虑前 i 项的最优解。
    转移逻辑：对第 i 项仅“选/不选”。若选 i，需满足兼容/容量约束，
    并继承合法前驱状态的最优值；若不选，直接继承 dp[i-1]。
    正确性：由最优子结构，全局最优解的任意前缀必为子问题最优。
    算法枚举所有合法前驱/兼容点，覆盖真实最优转移路径。
    按 i 递增计算保证无后效性，归纳得 dp[n] 为全局最优。

【复杂度直觉】

  • 正向：LIS 朴素 O(n²)；加权区间 O(n log n)（排序+二分求 p(i)）；Final Q3 O(n·D)（D=max deadline）。
  • 逆向反推：题干暗示 O(n log n) 且是序列最优 → 必用二分/单调栈优化转移。若约束含“相邻不能同时选” → 转移跳 i-2。若 n≤5000 → 接受 O(n²)；若 n≤10⁵ → 必须 O(n log n) 或 O(n)。
  • 考场陷阱：Final Q3 必须写“按 deadline 排序 + 紧密调度从 0 开始”，否则 t≤d_i 的逻辑不闭环，直接扣 5-8 分。

🔹 2. 区间 DP (矩阵链乘 / 多边形剖分 / 石子合并)

【识别信号】

  • “连续区间最优分割/合并”、“矩阵链乘”、“多边形三角剖分”、“第一刀切在哪”、“相邻元素合并代价”。
  • 真题映射：Assignment 2 多边形剖分、矩阵链乘法、石子合并。

【直觉类比】
“切链条/剥洋葱”。一根长链，第一刀必须选一个断点 k。切开后左右两段完全独立，递归处理。总代价 = 左段最优 + 右段最优 + 当前切割/合并的固有代价。就像切香肠，每一刀只影响当前段，左右互不干扰。

【数学骨架】

  • 状态：dp[i][j] = 闭区间 [i, j] 内元素的最优解
    (释义：强制锁定当前只关心从第 i 个到第 j 个连续元素的子问题，屏蔽外部干扰)
  • 转移：dp[i][j] = min/max_{i≤k<j} { dp[i][k] + dp[k+1][j] + cost(i, j, k) }
    (释义：k 是第一刀位置；dp[i][k] 左子链最优；dp[k+1][j] 右子链最优；cost 是切开后合并两段的固定开销)
  • 循环顺序：
    1
    2
    3
    4
    5
    6
    for len = 2 to n:          // 必须按区间长度从小到大！否则子问题未计算
        for i = 1 to n-len+1:
            j = i + len - 1
            dp[i][j] = ∞
            for k = i to j-1:
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + cost)
  • 变式 cost 映射：
    • 矩阵链乘：cost = p_{i-1}·p_k·p_j（维度乘积）
    • 多边形剖分：cost = dist(i,k) + dist(k,j)（k 范围改为 i<k<j）
    • 石子合并：cost = Σ_{t=i}^j w_t（区间和，需前缀和 O(1) 查询）

【证明模板】

  • 白话逻辑：最优子结构：全局最优分割点 k* 必使左右子区间各自最优。否则换掉差的那段，总结果会更优，矛盾。枚举完备性：任何合法剖分/合并必在某处断开。算法穷举所有 k，故必覆盖真实最优断点 k*。
  • 数学符号：设 OPT(i,j) 为区间最优值。若存在 k* 使 OPT(i,j) = OPT(i,k*) + OPT(k*+1,j) + cost，且左/右子区间解非最优，则可替换为更优子解，导致 OPT'(i,j) < OPT(i,j)，与定义矛盾。故子问题必最优。
  • 考场直接抄写骨架：
    1
    2
    3
    4
    5
    6
    状态定义：dp[i][j] 表示区间 [i,j] 的最优解。
    转移逻辑：枚举分割点 k，将区间拆为 [i,k] 与 [k+1,j]。
    总代价 = 左子区间最优 + 右子区间最优 + 当前合并/切割代价 cost。
    正确性：任何合法划分必在某 k 处断开。算法穷举 k∈[i,j-1]，
    必覆盖真实最优断点。由最优子结构，左右子区间解必最优，
    否则可替换得全局更优。按长度递增计算保证无后效性。

【复杂度直觉】

  • 正向：状态 O(n²) × 转移枚举 O(n) = O(n³)。空间 O(n²)。
  • 逆向反推：题干暗示 O(n³) 或 n≤500 → 直接锁定区间DP。若要求 O(n²) → 考虑四边形不等式优化（k 的决策单调性：opt[i][j-1] ≤ opt[i][j] ≤ opt[i+1][j]），或改为线性DP。看到“连续段/区间/合并”必试此模板。
  • 考场陷阱：多边形剖分 k 范围是 i<k<j（不能取端点，否则退化为边）；矩阵链乘 k 范围是 i≤k<j。写错范围扣 3-5 分。循环顺序必须写“按 len 递增”，否则逻辑不成立。

🔹 3. 0/1背包与伪多项式 DP (含 FPTAS)

【识别信号】

  • “n个物品选或不选”、“总重量≤W”、“最大化价值/最小化重量”、“物品不可分割”、“容量限制”。
  • 真题映射：Assignment 2 背包变种、FPTAS 近似算法、相邻约束背包。

【直觉类比】
“装箱记账本”。面对第 i 个物品，只有两条路：跳过它（继承上一行同容量），或装下它（价值+剩余容量的最优解）。容量是硬约束，必须写进状态。就像背包客，每见一件装备，只问自己：“带上它，剩下的空间还能装多少最优？”

【数学骨架】

  • 状态：dp[i][w] = 前 i 个物品，总重不超过 w 的最大价值
  • 转移：dp[i][w] = max(dp[i-1][w], v_i + dp[i-1][w-w_i]) （若 w≥w_i）
    (释义：dp[i-1][w] 不选 i；v_i + dp[i-1][w-w_i] 选 i，扣除重量 w_i 后查前 i-1 个物品的最优剩余价值)
  • 空间优化：一维数组倒序遍历
    for w=W down to w_i: dp[w] = max(dp[w], v_i + dp[w-w_i])
    (释义：倒序防止同一物品被重复选取。正序会变成完全背包)
  • 变式映射：
    • 相邻不能选：dp[i][w] = max(dp[i-1][w], v_i + dp[i-2][w-w_i])
    • 翻转DP（W极大但v小）：dp[i][v] = 达到价值 v 的最小重量，转移 min(dp[i-1][v], dp[i-1][v-v_i] + w_i)

【证明模板】

  • 白话逻辑：最优子结构：对物品 i 的决策独立于后续。若最优解含 i，则剩余容量 W-w_i 必由前 i-1 物品最优填充。归纳保证 dp[i][w] 覆盖所有子集组合。伪多项式：W 是数值非输入长度，二进制编码长度为 log W，故复杂度相对输入规模是指数级，但相对 W 是多项式。
  • 数学符号：设 S* 为最优子集。若 i∈S*，则 S*\{i} 必为容量 W-w_i 下前 i-1 物品的最优解。否则存在更优 S'，使 val(S')+v_i > val(S*)，矛盾。故转移正确。
  • 考场直接抄写骨架：
    1
    2
    3
    4
    5
    6
    状态定义：dp[i][w] 表示前 i 个物品，总重不超过 w 的最大价值。
    转移逻辑：对物品 i 仅“选/不选”。不选继承 dp[i-1][w]；
    选则需 w≥w_i，价值为 v_i + dp[i-1][w-w_i]。两者取 max。
    正确性：由最优子结构，若最优解含 i，则剩余容量必取子问题最优。
    一维倒序遍历保证每个物品仅用一次（防重复选取）。
    复杂度 O(nW) 为伪多项式（W 是数值，非输入编码长度）。

【复杂度直觉】

  • 正向：时间 O(nW)，空间 O(W)（优化后）。FPTAS 缩放后 O(n³/ε)。
  • 逆向反推：题干给“容量限制+不可分”必是背包。若 W 极大但价值 v_i 较小 → 翻转 DP。若要求近似解 → FPTAS（缩放价值 v_i' = ⌊v_i/k⌋，k=ε·v_max/2n，误差可控）。若题干暗示多项式时间但 W 指数级 → 必考 FPTAS 或贪心近似。
  • 考场陷阱：FPTAS 必须写清缩放参数 k 和误差界 ≥ OPT/(1+ε)。一维优化必须强调“倒序”，写正序直接判为完全背包扣一半分。

🔹 4. 树形 DP (Tree DP)

【识别信号】

  • “树结构/无环图”、“父子约束/相邻不选”、“子树最优”、“后序遍历/自底向上”、“最大权独立集/最小顶点覆盖”。
  • 真题映射：Assignment 变式、Lecture 树形约束题。

【直觉类比】
“自底向上汇报”。每个节点向父节点提交两套方案：“选我”和“不选我”。父节点根据子节点的汇报，组合出自己的两套方案。就像公司预算，每个部门经理汇总下属的最优方案，再决定自己部门的预算分配。

【数学骨架】

  • 状态：dp[u][0] = u 不选时子树最大权；dp[u][1] = u 选时子树最大权
  • 转移（DFS 后序遍历）：
    dp[u][1] = w(u) + Σ_{v∈children(u)} dp[v][0]
    dp[u][0] = Σ_{v∈children(u)} max(dp[v][0], dp[v][1])
    (释义：选 u 则所有子节点 v 必不能选（相邻约束）；不选 u 则子节点 v 可自由选择最优状态。Σ 累加所有子树贡献)
  • 初始化：叶子节点 dp[leaf][1]=w(leaf), dp[leaf][0]=0
  • 最终答案：max(dp[root][0], dp[root][1])

【证明模板】

  • 白话逻辑：树的最优子结构：子树之间无交叉边，决策完全独立。无环保证无后效性（子节点决策不影响父节点以上的合法性）。DFS 后序确保计算 u 时所有子节点 v 的 dp[v][0/1] 已收敛。
  • 数学符号：设 T_u 为 u 的子树。若 u∈S*，则 ∀v∈children(u), v∉S*，故 OPT(T_u|u选) = w(u) + ΣOPT(T_v|v不选)。若 u∉S*，则 v 无约束，OPT(T_u|u不选) = Σmax(OPT(T_v|v选), OPT(T_v|v不选))。归纳得证。
  • 考场直接抄写骨架：
    1
    2
    3
    4
    5
    6
    状态定义：dp[u][0/1] 表示 u 不选/选时，其子树的最大权重和。
    转移逻辑：选 u 则子节点必不选，累加 dp[v][0]；
    不选 u 则子节点自由选优，累加 max(dp[v][0], dp[v][1])。
    正确性：树结构无环，子树决策相互独立，满足最优子结构。
    DFS 后序遍历保证计算父节点时子节点状态已完全收敛。
    相邻约束由状态转移天然编码，归纳得全局最优。

【复杂度直觉】

  • 正向：每个节点访问一次，转移耗时正比于度数。总时间 O(n)。空间 O(n)（递归栈+DP表）。
  • 逆向反推：题干给“树+局部约束”必考树形DP。若带额外维度（如树上背包/限选k个）→ O(nk) 或 O(n²)（子树合并复杂度）。若图非树但有环 → 先缩点/破环成树，或转一般图DP/NP。
  • 考场陷阱：必须写“DFS后序/自底向上”。若写BFS或前序，状态未收敛直接0分。相邻约束题务必区分 dp[u][0] 和 dp[u][1] 的转移差异。

🔹 5. 状态压缩 DP (Bitmask DP)

【识别信号】

  • “n≤20 / m≤12”、“棋盘/网格放置”、“相邻/轮廓线约束”、“状态可用二进制表示”、“骨牌覆盖/互不攻击”。
  • 真题映射：Assignment 2 棋盘放石子、Lecture 轮廓线DP。

【直觉类比】
“逐行铺砖/填格子”。当前行状态只依赖上一行状态，用二进制位记录占用情况（1=占，0=空）。就像扫地机器人，只记“当前这一排哪里脏了”，根据上一排的清洁记录决定这一排怎么扫。

【数学骨架】

  • 状态：dp[i][mask] = 前 i 行，第 i 行放置状态为 mask 时的最优解/方案数
    (释义：mask 是 m 位二进制数，第 j 位为 1 表示 (i,j) 被占用/放置)
  • 转移：dp[i][mask] = Σ/max(dp[i-1][prev_mask] + val)
    约束：compatible(mask, prev_mask) == True
    (释义：兼容性检查通常用位运算：(mask & prev_mask) == 0 表示上下不冲突；(mask & (mask<<1)) == 0 表示左右不冲突)
  • 初始化：dp[0][0] = 1（或 0），其余 -∞
  • 最终答案：Σ dp[n][mask] 或 max dp[n][mask]

【证明模板】

  • 白话逻辑：状态空间穷举+兼容性剪枝。轮廓线（当前行与上一行交界）包含所有影响未来决策的历史信息，满足无后效性。位运算 O(1) 检查合法性，避免无效状态扩展。
  • 数学符号：设 S_i 为第 i 行合法状态集。dp[i][m] = opt_{m'∈S_{i-1}, compat(m,m')} {dp[i-1][m'] + cost(m)}。由马尔可夫性，第 i 行决策仅依赖 i-1 行状态 m'，更早行状态已被 m' 压缩吸收。
  • 考场直接抄写骨架：
    1
    2
    3
    4
    5
    6
    状态定义：dp[i][mask] 表示前 i 行，第 i 行状态为 mask 的最优值。
    转移逻辑：枚举上一行状态 prev_mask，若 compatible(mask, prev_mask)
    则 dp[i][mask] = opt(dp[i-1][prev_mask] + val)。
    兼容性用位运算检查：(mask & prev_mask)==0 等。
    正确性：轮廓线包含所有影响后续决策的历史信息，满足无后效性。
    状态压缩将指数级配置映射为整数，位运算 O(1) 剪枝非法转移。

【复杂度直觉】

  • 正向：状态数 n·2^m，转移枚举 2^m，总 O(n·4^m)。实际合法状态远少于 2^m，常数极小。空间 O(2^m)（可滚动数组）。
  • 逆向反推：题干 n/m≤12~20 → 必状压。若要求路径/排列 → TSP 变式 dp[mask][u]。若网格宽 m 固定 → 复杂度对 m 指数，对 n 线性。
  • 考场陷阱：必须写“位运算兼容性检查”。漏写 (mask & prev_mask)==0 扣逻辑分。滚动数组优化需注明“只保留上一行”。TSP 状态是 dp[mask][u]（已访问集合mask，当前在u），别和棋盘混淆。

🔹 6. 二维/网格 DP (布料切割 / 矩形分割)

【识别信号】

  • “矩形切割/二维资源分配”、“Guillotine切割(一刀切到底)”、“子矩阵最优/路径计数”、“最大化收益/最小化浪费”。
  • 真题映射：Assignment 2 布料切割 (Cloth Cutting)、Lecture 二维DP。

【直觉类比】
“切巧克力/铺地毯”。横切或竖切一刀，分成两个独立子矩形递归。总收益 = 左块最优 + 右块最优。就像裁缝剪布，每一刀必须贯穿整块，剪开后两块布独立处理，互不影响。

【数学骨架】

  • 状态：dp[i][j] = i×j 矩形的最优收益/最小代价
  • 转移：
    1
    2
    3
    4
    5
    dp[i][j] = max(
        price[i][j],                          // 不切，直接做成产品
        max_{1≤k<i} (dp[k][j] + dp[i-k][j]),  // 横切，分成 k×j 和 (i-k)×j
        max_{1≤k<j} (dp[i][k] + dp[i][j-k])   // 竖切，分成 i×k 和 i×(j-k)
    )
    (释义：price[i][j] 是预处理的产品售价（含旋转）；横/竖切枚举切割线 k，取左右子矩形最优和。Guillotine 约束保证每次一刀切到底)
  • 初始化：dp[i][j] = price[i][j]（基础值）
  • 循环顺序：i 从 1 到 X，j 从 1 到 Y（从小到大，保证子矩形已计算）

【证明模板】

  • 白话逻辑：最优子结构：第一刀必在某个横/竖位置 k。切开后两子矩形独立，各自必取最优。枚举所有 k 必含全局最优切割线。Guillotine 约束排除 L 型等复杂切割，保证 DP 可行性。
  • 数学符号：设 OPT(i,j) 为 i×j 最优值。若最优方案第一刀为横切 k，则 OPT(i,j) = OPT(k,j) + OPT(i-k,j)。若为竖切同理。若不切则 OPT(i,j)=price[i,j]。取 max 覆盖所有合法首刀，归纳得证。
  • 考场直接抄写骨架：
    1
    2
    3
    4
    5
    6
    7
    状态定义：dp[i][j] 表示 i×j 矩形的最大收益。
    转移逻辑：三种决策取 max：1.不切直接卖(price[i][j])；
    2.横切枚举 k，收益 dp[k][j]+dp[i-k][j]；
    3.竖切枚举 k，收益 dp[i][k]+dp[i][j-k]。
    正确性：Guillotine 切割保证每刀将矩形分为两个独立子矩形。
    由最优子结构，子矩形必取各自最优解。枚举所有切割线 k
    覆盖真实最优首刀。按尺寸递增计算保证无后效性。

【复杂度直觉】

  • 正向：状态 O(XY)，横切枚举 O(X)，竖切枚举 O(Y)。总 O(X²Y + XY²)。若 X,Y≈n → O(n³)。空间 O(XY)。
  • 逆向反推：题干给“矩形切割+一刀切到底”必考此模板。若允许任意形状切割（非 Guillotine）→ NP-Hard，需转最大流/近似。若尺寸≤200 → O(n³) 可接受。
  • 考场陷阱：必须预处理 price[i][j] 并处理旋转（price[a][b]=price[b][a]=max(...)）。漏写“不切直接卖”选项扣 5 分。循环顺序必须“从小到大”，否则子问题未计算。

Part 3: 图论基础与最短路径

🔹 1. BFS 与 DFS (图遍历与环检测)

【识别信号】

  • “连通性/遍历所有可达点/找路径/检测环/无权图最短跳数/层序遍历”
  • 真题映射：基础遍历、DFS回边判环、BFS求无权最短路。

【直觉类比】

  • BFS：水波纹扩散。从起点一圈圈往外推，先到的点一定跳数最少。用队列维护“待探索边界”。
  • DFS：走迷宫摸墙。一条路走到黑，撞墙就回溯。用递归栈维护“当前路径”。天然适合找连通分量、拓扑序、检测回边。

【数学骨架】

  • BFS：
    1
    2
    3
    4
    5
    6
    7
    Q.enqueue(s), visited[s]=True, dist[s]=0
    while Q not empty:
        u = Q.dequeue()
        for v in adj[u]:
            if not visited[v]:
                visited[v]=True, dist[v]=dist[u]+1, parent[v]=u
                Q.enqueue(v)
  • DFS：
    1
    2
    3
    4
    5
    visited[u]=True, pre[u]=++timer
    for v in adj[u]:
        if not visited[v]: parent[v]=u, DFS(v)
        else if v != parent[u]: 发现回边 → 有环
    post[u]=++timer
    (释义：pre/post 记录进出时间戳，用于拓扑/SCC；parent 防无向图误判回边；有向图环检测只需 visited[v] && v在递归栈中)

【证明模板】

  • 白话逻辑：BFS按层扩展，第k层节点距离起点恰为k。若存在更短路径，必在更早层被访问，矛盾。DFS连通性：若u,v连通但v未访问，路径上必存在已访问点x指向未访问点y，DFS必会探索y，矛盾。环检测：DFS遇到指向当前递归栈内节点的回边，说明形成闭环。
  • 数学符号：BFS归纳：设第i层节点集为L_i。初始化L_0={s}。若L_i中所有点dist=i，则其未访问邻居必在L_{i+1}且dist=i+1。由队列FIFO性质，层序严格递增。
  • 考场直接抄写骨架：
    1
    2
    3
    4
    BFS正确性：按距离起点跳数分层扩展。队列FIFO保证先入队节点距离≤后入队节点。
    若v在第k层被访问，则dist[v]=k。假设存在更短路径<k，则v必在更早层被访问，矛盾。
    DFS环检测：维护递归栈onStack[]。遍历边(u,v)时，若v已访问且onStack[v]=True，
    说明v是u的祖先，形成回边(u,v)，图含环。无向图需排除父节点回边。

【复杂度直觉】

  • 正向：O(V+E)。每个顶点入队/入栈1次 O(V)，每条边被检查2次（无向）或1次（有向）O(E)。
  • 逆向反推：题干要求 O(V+E) 且涉及连通/遍历/依赖 → 必是BFS/DFS线性扫描。若求无权最短路 → BFS。若求依赖顺序/判环 → DFS。
  • 考场陷阱：有向图判环必须用 onStack（或 post 时间戳），仅用 visited 会误判交叉边为环。BFS求最短路仅适用于无权图或边权相等，带权图必须用 Dijkstra/BF。

🔹 2. 拓扑排序 (Topological Sort)

【识别信号】

  • “DAG/依赖关系/先修课程/执行顺序/无环有向图线性排序/所有边从左指向右”
  • 真题映射：任务调度前置约束、DAG上DP预处理。

【直觉类比】
“拆积木/排课表”。每次只能拆没有前置依赖的积木块（入度为0）。拆掉后，它指向的积木依赖数减1。重复直到拆完。如果最后还有积木剩着，说明有死锁（环）。

【数学骨架】

  • Kahn算法（入度队列法）：
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    计算所有点入度 indeg[v]
    Q = {v | indeg[v] == 0}
    order = []
    while Q not empty:
        u = Q.dequeue()
        order.append(u)
        for v in adj[u]:
            indeg[v]--
            if indeg[v] == 0: Q.enqueue(v)
    if len(order) < V: 存在环，无拓扑序
    else: 返回 order
    (释义：indeg[v] 记录前置任务数。入度0表示无依赖可立即执行。删点减度模拟“完成前置释放后续”。最终点数<V说明有环卡死)

【证明模板】

  • 白话逻辑：DAG必存在入度为0的点（否则沿入边逆推无限长，必成环）。贪心选择入度0点不破坏任何依赖（它无前置）。删除后子图仍为DAG，归纳可排完。若排不完，剩余子图每个点入度≥1，逆推必含环。
  • 数学符号：设G为DAG。∃v, indeg(v)=0。取v为序列首元素，G'=G{v}仍为DAG。由强归纳，G'可拓扑排序，故G可排序。若算法终止时|order|<V，则剩余子图H中∀u∈H, indeg_H(u)≥1。任取u_0，沿入边逆推u_1,u_2,...，因V有限必重复，构成环，与DAG矛盾。
  • 考场直接抄写骨架：
    1
    2
    3
    4
    算法：计算入度，入度0点入队。循环弹出u加入序列，邻居入度-1，若为0入队。
    正确性：DAG必存在入度0顶点。每次选择入度0点不违反任何依赖约束。
    删除后子图仍为DAG，归纳可得完整拓扑序。若最终序列长度<V，
    说明剩余子图所有点入度≥1，沿入边逆推必形成环，故原图非DAG。

【复杂度直觉】

  • 正向：O(V+E)。计算入度扫全图 O(V+E)，每个点入队出队1次 O(V)，每条边触发1次减度 O(E)。
  • 逆向反推：题干给“依赖/先修/执行顺序”必考拓扑。若问“拓扑序是否唯一” → 检查队列中是否同时存在>1个元素（多选择则序不唯一）。若需在DAG上求最长/最短路 → 先拓扑排序，再按序DP松弛 O(V+E)。
  • 考场陷阱：必须写“若最终序列长度<V则存在环”。漏写环检测扣逻辑分。DFS逆后序（post时间戳降序）也是拓扑序，但Kahn法更易写且天然判环。

🔹 3. 强连通分量 (SCC / Kosaraju算法)

【识别信号】

  • “有向图/互相可达/缩点/元图DAG/加边最少强连通/Assignment 3 Q2”
  • 真题映射：Assignment 3 Q2 (连通性/加边)、元图Source/Sink计数。

【直觉类比】
“找小团体”。团体内的人互相认识（互达），团体之间只有单向关系。把每个团体缩成一个点，整个图变成有向无环图（DAG）。Kosaraju的魔法：反转所有箭头不改变团体内部，但反转了团体间的方向。先按“谁最后死”排序，再在反图里抓人，一抓就是一个完整团体。

【数学骨架】

  • Kosaraju三步：
    1. DFS原图 G，记录每个点 finish[u]（出栈时间）。
    2. 构造反图 G^R（所有边反向）。
    3. 按 finish 降序依次对 G^R 中未访问点做DFS。每次DFS遍历到的点集构成一个SCC。
      (释义：finish最大的点必在G的“源SCC”中。反图G^R中源SCC变成“汇SCC”。在G^R中从汇SCC开始DFS，恰好只能遍历该SCC内部，不会漏出到其他SCC。剥洋葱式逐个剥离)

【证明模板】

  • 白话逻辑：核心引理：finish时间最大的顶点必属于G的某个源SCC（无入边SCC）。在反图G^R中，源SCC变为汇SCC（无出边）。从汇SCC任一点DFS，只能到达该SCC内部点（无法跨出）。记录该SCC后删除，剩余图仍满足性质。归纳可剥离所有SCC。
  • 数学符号：设C为G中源SCC。∀u∈C, v∉C，若u可达v，则finish(u)>finish(v)（DFS先深入v回溯后才回溯u）。故max finish必在源SCC。在G^R中，C变为汇SCC（无出边指向其他SCC）。DFS_G^R(x) (x∈C) 仅访问C内点。算法正确分割。
  • 考场直接抄写骨架：
    1
    2
    3
    4
    5
    6
    算法：1.DFS原图G记录finish时间；2.建反图G^R；3.按finish降序DFS G^R，
    每次DFS树即为一个SCC。
    正确性：finish最大的点必属于G的源SCC。在反图G^R中源SCC变为汇SCC，
    从其中任一点DFS仅能遍历该SCC内部，不会跨越到其他分量。
    剥离后剩余图性质不变，归纳可正确划分所有SCC。
    缩点后元图必为DAG（若元图有环，则环上SCC应合并为一个，矛盾）。

【复杂度直觉】

  • 正向：O(V+E)。两次DFS各 O(V+E)，建反图 O(V+E)。总线性。
  • 逆向反推：题干给“互相可达/缩点/加边强连通”必考SCC。Assignment 3 Q2直接考：缩点后统计元图入度0点(Source)和出度0点(Sink)。使全图强连通最少加边数 = max(Source数, Sink数)。使s可达全图最少加边数 = s所在SCC外的Source数。
  • 考场陷阱：必须强调“元图是DAG”。若题目问“谁能到达所有点”，答“仅当元图唯一Source时，该Source内所有点可达全图”。漏写DAG性质或Source/Sink定义扣步骤分。

🔹 4. Dijkstra (单源最短路 / 非负权)

【识别信号】

  • “单源最短路/边权≥0/最快到达/最小代价路径/Final Q2航班调度底层逻辑”
  • 真题映射：Final Q2 (按时间松弛本质是DAG上的Dijkstra变种)、正权图最短路。

【直觉类比】
“贪心扩张领地”。维护一个“已确定最短距离的集合S”。每次从未确定点中挑离起点最近的，把它拉进S（锁定，永不反悔）。然后用它更新邻居的距离。因为边权非负，绕远路不可能更短，所以锁定是安全的。

【数学骨架】

  • 优先队列实现：
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    dist[v]=∞ ∀v, dist[s]=0
    PQ.push((0, s))
    while PQ not empty:
        (d, u) = PQ.pop()
        if d > dist[u]: continue  // 过期条目跳过
        for (v, w) in adj[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                parent[v] = u
                PQ.push((dist[v], v))
    (释义：dist[u] 维护当前已知最短距离。PQ按dist小顶堆排序。d>dist[u] 过滤旧松弛记录。松弛操作尝试用u缩短v。非负权保证首次弹出u时dist[u]已收敛)

【证明模板】

  • 白话逻辑：归纳法证明“每次弹出u时，dist[u]必为真实最短路”。基始s成立。假设S中点已锁定。设u是PQ中dist最小点。若存在更短路径P，P必离开S进入未访问区，设离开点为y。由非负权，P到y的距离≥dist[y]≥dist[u]（u是PQ最小）。故P不可能比dist[u]短，矛盾。
  • 数学符号：设S为已锁定集合。归纳假设∀x∈S, dist[x]=δ(s,x)。取u=argmin_{v∉S} dist[v]。假设δ(s,u)<dist[u]。设最短路径P首次离开S的边为(x,y)，x∈S,y∉S。则δ(s,u)=δ(s,y)+δ(y,u)≥dist[y]+0≥dist[u]（因y∉S且u最小）。矛盾。故dist[u]=δ(s,u)。
  • 考场直接抄写骨架：
    1
    2
    3
    4
    5
    算法：维护dist数组与最小堆PQ。初始dist[s]=0入堆。循环弹出最小dist点u，
    若dist[u]已锁定则跳过；否则松弛邻居v：若dist[u]+w<dist[v]则更新并入堆。
    正确性：由数学归纳法，每次从PQ弹出u时dist[u]必为全局最短。
    假设存在更短路径，必经过某未锁定边界点y。由边权非负，
    dist[y]≤路径长≤dist[u]，与u是PQ最小值矛盾。故贪心锁定安全。

【复杂度直觉】

  • 正向：二叉堆 O((V+E)log V)。Fibonacci堆 O(VlogV + E)。空间 O(V+E)。
  • 逆向反推：题干给“正权最短路/单源”必考Dijkstra。若图是DAG → 可拓扑排序后线性松弛 O(V+E)（Final Q2本质）。若含负权 → Dijkstra直接失效（贪心锁定被负权退款打破），必须换Bellman-Ford。
  • 考场陷阱：必须写“边权非负是正确性前提”。若题目隐含负权（如“优惠/退款/时间倒流”），用Dijkstra直接0分。PQ实现必须写 if d > dist[u]: continue 过滤过期条目，否则复杂度退化。

🔹 5. Bellman-Ford (单源最短路 / 含负权与负环)

【识别信号】

  • “含负权边/检测负环/最多k条边最短路径/Assignment 3 Q1”
  • 真题映射：Assignment 3 Q1 (限制k边最短路)、负权图、负环检测。

【直觉类比】
“动态规划按边数松弛”。第1轮保证找到最多1条边的最短路，第2轮保证最多2条边… 第V-1轮保证找到所有最短路（无负环时最短路最多V-1条边）。像水波慢慢渗透，允许“负权退款”。如果第V轮还能缩短，说明有“无限提款机”（负环）。

【数学骨架】

  • 标准BF：
    1
    2
    3
    4
    5
    6
    7
    8
    dist[v]=∞ ∀v, dist[s]=0
    for i = 1 to V-1:
        for each edge (u, v, w) in E:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
    // 负环检测
    for each edge (u, v, w) in E:
        if dist[u] + w < dist[v]: return "存在负环"
  • Assignment 3 Q1 变式（最多k边）：外层循环改为 for i = 1 to k。其余不变。复杂度 O(kE)。
    (释义：第i轮松弛后，dist[v]存储的是从s到v最多经过i条边的最短路径。无负环时最短路≤V-1边，故V-1轮收敛。k边限制直接截断循环)

【证明模板】

  • 白话逻辑：归纳法：第i轮结束后，∀v, dist[v] ≤ 最多i条边的s→v最短路径。基始i=0成立。第i轮遍历所有边，若最短路径含i条边，其前i-1条边已在上一轮收敛，本轮最后一条边被松弛，故dist更新。无负环时最短路无重复点，边数≤V-1，故V-1轮后全局收敛。第V轮仍松弛说明路径可无限缩短，必含负环。
  • 数学符号：设δ_i(v)为最多i条边的最短路径长。归纳假设第i-1轮后dist[v]≤δ_{i-1}(v)。对最短路径P=(v_0,...,v_i)，边(v_{i-1},v_i)在本轮被检查。dist[v_i] ≤ dist[v_{i-1}]+w ≤ δ_{i-1}(v_{i-1})+w = δ_i(v_i)。故第i轮后dist[v]≤δ_i(v)。
  • 考场直接抄写骨架：
    1
    2
    3
    4
    5
    6
    算法：初始化dist[s]=0。循环V-1次，每次遍历所有边执行松弛：
    若dist[u]+w<dist[v]则更新dist[v]。第V次遍历若仍能松弛，则存在负环。
    正确性：由归纳法，第i轮松弛后dist[v]存储最多i条边的最短路径。
    无负环时最短路不含重复顶点，边数≤V-1，故V-1轮后dist收敛至全局最优。
    若第V轮仍可松弛，说明存在路径可无限降低代价，必含负权环。
    变式：若限制最多k条边，外层循环改为k次，复杂度O(kE)。

【复杂度直觉】

  • 正向：O(VE)。外层V-1轮，内层扫E条边。空间 O(V)。
  • 逆向反推：题干给“含负权/负环检测/最多k边”必考BF。Assignment 3 Q1直接考k边变种（只跑k轮）。若图稠密 E≈V^2 → O(V^3)。若要求多项式但含负权 → BF是唯一选择。
  • 考场陷阱：必须写“第V轮检测负环”。若题目问“如何检测全图负环（不仅s可达）” → 答“加超级源点s'连所有点权0，跑BF”。k边变种不能用Dijkstra+状态（除非k极小），BF天然支持。

🔹 6. Floyd-Warshall (全源最短路 / 传递闭包)

【识别信号】

  • “所有点对最短路/稠密图/传递闭包/中间节点限制/动态规划图论”
  • 真题映射：全源查询、可达性矩阵、小规模图(V≤500)多源最短路。

【直觉类比】
“动态规划按跳板扩张”。k 是允许使用的最大中间节点编号。考虑点k后，i到j的最短路要么不走k（继承旧值），要么走k（i→k + k→j）。三重循环慢慢放开“允许经过的点集”，最终所有点都可作跳板。

【数学骨架】

  • 标准FW：
    1
    2
    3
    4
    5
    初始化 D[i][j] = w(i,j) (若无边=∞, i=j=0)
    for k = 1 to V:
        for i = 1 to V:
            for j = 1 to V:
                D[i][j] = min(D[i][j], D[i][k] + D[k][j])
    (释义：D[i][j] 维护当前允许经{1..k}中间点的最短路。k必须是最外层循环！保证计算k时，i→k和k→j已基于{1..k-1}收敛。顺序错直接逻辑崩溃)

【证明模板】

  • 白话逻辑：归纳k：D_k[i][j] 表示仅经中间点{1..k}的i→j最短路。基始k=0为直连边。考虑k时，最优路径要么不经过k（值=D_{k-1}[i][j]），要么经过k（拆为i→k和k→j，两者中间点仅含{1..k-1}，值=D_{k-1}[i][k]+D_{k-1}[k][j]）。取min覆盖所有情况。
  • 数学符号：设 d_{ij}^{(k)} 为中间点∈{1..k}的最短路长。d_{ij}^{(0)} = w_{ij}。转移：d_{ij}^{(k)} = min(d_{ij}^{(k-1)}, d_{ik}^{(k-1)} + d_{kj}^{(k-1)})。由最优子结构，i→j经k的最短路必由i→k和k→j最优拼接。归纳得 d_{ij}^{(V)} = δ(i,j)。
  • 考场直接抄写骨架：
    1
    2
    3
    4
    5
    6
    7
    算法：初始化距离矩阵D。三重循环k,i,j：
    D[i][j] = min(D[i][j], D[i][k] + D[k][j])。
    正确性：令D_k[i][j]为仅经{1..k}中间点的最短路。归纳k：
    考虑点k时，i→j最优路径要么不经k（继承D_{k-1}[i][j]），
    要么经k（拆为i→k与k→j，中间点仅含{1..k-1}）。
    转移方程覆盖两种情况，k为最外层保证子问题已收敛。
    最终D_V[i][j]为全局全源最短路。

【复杂度直觉】

  • 正向：O(V^3)，空间 O(V^2)。三重循环严格 V^3 次操作。
  • 逆向反推：题干给“全源/稠密图/传递闭包/V≤500”必考FW。若求传递闭包（可达性） → 改min为OR，改+为AND：R[i][j] = R[i][j] | (R[i][k] & R[k][j])。若V>1000 → FW超时，需换n次Dijkstra O(V(V+E)logV)。
  • 考场陷阱：k必须是最外层循环！写错顺序直接0分。若图含负环，FW仍可跑，但 D[i][i] < 0 表示i在负环上。必须写“k为中间点枚举顺序，不可交换”。

Part 4: 最大流/最小割/贪心证明

🔹 1. Ford-Fulkerson / Edmonds-Karp & 残量网络

【识别信号】

  • “最大吞吐量/网络容量/瓶颈限制/增广路径/残量图/反向退流”
  • 真题映射：最大流基础、Assign 4 Q2 残量网络理论、Final 流网络题型。

【直觉类比】
“水管网找路灌水”。正向管道剩多少容量，就能往前灌多少；反向管道已经流了多少，就能“退水”多少（允许反悔）。只要从水源 $s$ 到水池 $t$ 还能找到一条有剩余容量的路，就拼命往里灌水，直到所有路都被“满流”或“零流”焊死，再也过不去为止。

【数学骨架】

  • 残量网络 $G_f$：对原图每条边 $(u,v)$ 容量 $c$，当前流 $f$。
    • 正向残量边：$c_f(u,v) = c(u,v) - f(u,v)$（还能流多少）
    • 反向残量边：$c_f(v,u) = f(u,v)$（能退回多少）
      (释义：反向边是算法灵魂，允许“撤销错误分配”，保证最终收敛到全局最大流)
  • 增广路径 $p$：$G_f$ 中 $s \leadsto t$ 的任意路径。
  • 瓶颈容量：$c_f(p) = \min_{(u,v)\in p} c_f(u,v)$
  • 流更新：沿 $p$ 推送 $c_f(p)$ 单位流。正向边 $f \leftarrow f + c_f(p)$，反向边 $f \leftarrow f - c_f(p)$。
  • Edmonds-Karp (EK)：强制用 BFS 找边数最少的增广路，保证多项式时间。

【证明模板】

  • 白话逻辑：最大流最小割定理。流值永远 $\le$ 任意割容量。当 $G_f$ 中 $s$ 到 $t$ 无路时，定义 $A={v \mid s\leadsto v \text{ in } G_f}$，$B=V\setminus A$。此时所有 $A\to B$ 边必满流（否则残量>0，$v$ 应属 $A$），所有 $B\to A$ 边必零流（否则反向残量>0，$u$ 应属 $A$）。故当前流值 $= c(A,B)$，达到理论上界，必为最大流。
  • 数学符号：设 $f$ 为算法终止流。$A={v \mid s \xrightarrow{G_f} v}$。$\forall (u,v)\in E, u\in A, v\in B \Rightarrow c_f(u,v)=0 \Rightarrow f(u,v)=c(u,v)$。$\forall (v,u)\in E, v\in B, u\in A \Rightarrow c_f(v,u)=0 \Rightarrow f(v,u)=0$。故 $|f| = \sum_{u\in A, v\in B} f(u,v) - \sum_{v\in B, u\in A} f(v,u) = c(A,B)$。由弱对偶 $|f| \le \min\text{-cut} \le c(A,B) = |f|$，得 $|f| = \max\text{-flow} = \min\text{-cut}$。
  • 考场直接抄写骨架：
    1
    2
    3
    4
    5
    算法：在残量网络 G_f 中反复寻找 s→t 增广路径 p，沿 p 推送瓶颈容量 c_f(p)，
    更新正向/反向边流量，直至 G_f 中 s 无法到达 t。EK 算法用 BFS 找最短增广路。
    正确性：算法终止时，令 A 为 G_f 中 s 可达点集，B=V\A。由定义，A→B 边残量为0
    （满流），B→A 边反向残量为0（零流）。故当前流值 |f| = c(A,B)。
    由最大流最小割定理，任意流值 ≤ 任意割容量，故 |f| 达到理论上界，必为最大流。

【复杂度直觉】

  • 正向：FF 伪多项式 $O(m \cdot C_{max})$（整数流每次至少+1）。EK 严格 $O(n m^2)$（BFS限制增广次数 $\le O(nm)$）。Dinic $O(n^2 m)$（一般图极快）。
  • 逆向反推：题干给“整数容量/小数值”可用 FF；一般图/考试要求多项式必写 EK 或 Dinic。若考理论性质，重点写“残量网络断连 $\iff$ 达到最小割”。
  • 考场陷阱：必须写“反向边允许退流/反悔”。漏写反向边定义扣核心逻辑分。EK 必须强调“BFS找最短路径”，写DFS退化回FF。

🔹 2. 最大流建模万能模板 (资源分配/匹配/覆盖)

【识别信号】

  • “分配/匹配/覆盖/容量限制/是否可行/最多完成数/胜场分配/图定向”
  • 真题映射：Assign 4 Q3(足球出线)、Q4(d-orientable)、Final 匹配/分配题。

【直觉类比】
“水流分配系统”。源点供水（物品/任务/胜场）→ 管道分流（分配规则）→ 汇点收水（容器/队伍/顶点）。阀门容量 = 业务上限。满流 = 所有物品合法分配完毕；卡住 = 必有人超限或无法分配。

【数学骨架】

  • 三层图结构：
    1. s → 物品节点 i，容量 = 供给量/产生量
    2. 物品 i → 容器 j，容量 = ∞（或规则限制，如仅当兼容时连边）
    3. 容器 j → t，容量 = 接收上限/硬约束
  • 判定条件：计算最大流 $F$。若 $F == \text{总供给量}$ $\Rightarrow$ Yes（全部分配合法）；否则 $\Rightarrow$ No。
  • 变式映射：
    • 足球出线 (Assign 4 Q3)：物品=剩余比赛胜场，容器=队伍。s→比赛(场数)，比赛→两队(∞)，队伍→t(W_z-w_x)。满流 $\iff$ z能并列第一。
    • 图定向 (Assign 4 Q4)：物品=无向边，容器=顶点。s→边节点(1)，边→两端点(1)，顶点→t(d)。满流 $\iff$ 存在入度≤d的定向。
      (释义：中间层容量∞表示“单件物品分配比例无限制”，硬约束全压在汇点阀门上。流量守恒天然保证“每件物品必分且仅分一次”)

【证明模板】

  • 白话逻辑：构造双向映射。若原问题有合法分配方案，按方案将水流从s经物品推至对应容器，必不超汇点容量，故存在值为总供给的流。若最大流满流，由流量守恒，每件物品流量必全部分配给合法容器；由汇点容量限制，每个容器接收量不超上限。故流方案直接翻译为合法分配方案。
  • 数学符号：设供给总量 $R$。若存在分配 $x_{ij}$ 满足 $\sum_j x_{ij}=S_i$, $\sum_i x_{ij} \le C_j$，令 $f(s,i)=S_i, f(i,j)=x_{ij}, f(j,t)=\sum_i x_{ij}$，满足容量与守恒，故 $|f|=R$。反之若 $|f|=R$，由守恒 $f(i,j)$ 构成合法分配，且 $f(j,t)\le C_j$ 满足上限。
  • 考场直接抄写骨架：
    1
    2
    3
    4
    5
    建图：源点s连物品节点(容量=供给)，物品连兼容容器(容量=∞)，容器连汇点t(容量=上限)。
    判定：若 max_flow == 总供给量，输出 Yes，否则 No。
    正确性：流量守恒保证每件物品被完整分配且不凭空产生；汇点容量限制保证
    每个容器接收量不超业务上限。满流等价于所有物品均找到合法归属，
    构造双向映射可知流方案与原问题可行解一一对应。

【复杂度直觉】

  • 正向：节点 $O(V+E)$，边 $O(E)$。跑 EK/Dinic 均为多项式时间。
  • 逆向反推：看到“分配+上限+是否可行”直接画三层图，别犹豫。若题目问“如何输出具体方案”，答“检查中间边流量，$f(i,j)>0$ 表示物品i分配给容器j”。
  • 考场陷阱：必须写清每条边的物理意义和容量公式。漏写“满流判定条件”扣50%分。足球题必须预处理 $W_z$ 并剪枝 $w_x > W_z$。

🔹 3. 最小割性质与残量网络可达性 (Final Q4 / Assign 4 Q2)

【识别信号】

  • “残量网络/最小割分类/扩容是否增流/Source-Sink集合/割边性质/理论证明”
  • 真题映射：Final Q4 (Type-1/Type-2边扩容)、Assign 4 Q2 (v∈A必在任意最小割A'中)。

【直觉类比】
“大坝定律”。最小割就是一道焊死的墙。墙外($A$)水能到，墙内($B$)水过不去。扩容墙上的管子：如果墙后是死胡同($B\setminus T$，到不了终点)，水过去也卡住，流量不增；如果墙后能通终点($T$)，水就能一路流到 $t$，打通新増广路，流量必增。

【数学骨架】

  • 集合定义（最大流终止时的 $G_f$）：
    • $A = {v \mid s \leadsto v \text{ in } G_f}$（源侧可达集）
    • $B = V \setminus A$（汇侧不可达集）
    • $T = {v \in B \mid v \leadsto t \text{ in } G_f}$（B中能到t的点）
  • 边分类（跨越割 $(A,B)$ 的边 $e=(u,v), u\in A, v\in B$）：
    • Type-1：$v \in T$（墙后通终点）
    • Type-2：$v \in B \setminus T$（墙后是死胡同）
  • 核心性质：$(A,B)$ 是最小割。$A\to B$ 满流(残量0)，$B\to A$ 零流(反向残量0)。$G_f$ 中无任何 $A\to B$ 的边。

【证明模板】

  • 白话逻辑：反证法+残量网络断连性。最小割 $\Rightarrow$ $A\to B$ 满流，$B\to A$ 零流 $\Rightarrow$ $G_f$ 中 $A$ 到 $B$ 的路全焊死。扩容Type-1边 $(u,v)$：$s\leadsto u$ (因$u\in A$)，$v\leadsto t$ (因$v\in T$)，扩容后残量>0，打通 $s\to u\to v\to t$ 增广路 $\Rightarrow$ 必增流(True)。扩容Type-2边：$v$ 到不了 $t$，水卡在 $v$，无法形成 $s\to t$ 路径 $\Rightarrow$ 不增流(False)。任意最小割 $(A',B')$ 必满足 $A \subseteq A' \subseteq V\setminus T$，故Type-2边必跨割。
  • 数学符号：由 max-flow=min-cut，$\forall (x,y)\in E, x\in A', y\in B' \Rightarrow f(x,y)=c(x,y)$；$\forall (y,x), y\in B', x\in A' \Rightarrow f(y,x)=0$。故 $G_f$ 中 $c_f(x,y)=0, c_f(y,x)=0$，无 $A'\to B'$ 路径。若 $v\in A$ 但 $v\in B'$，则 $s\in A'$ 无法在 $G_f$ 中到达 $v$，与 $v\in A$ 矛盾。故 $A\subseteq A'$。
  • 考场直接抄写骨架：
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    (a) Type-2扩容必增流？False。v∈B\T 说明 G_f 中 v 无法到达 t。
        扩容 (u,v) 仅增加 A→B 残量，但水流至 v 后无路通向 t，无法形成 s→t 增广路径，
        最大流不变。
    (b) 找新最小割：在 G_f 中从 t 反向 BFS/DFS 得集合 T。令 A'=A∪T, B'=V\A'。
        因 A 与 T 在 G_f 中无正容量边相连，(A',B') 仍为饱和割，容量等于原最小割，
        且 A'≠A，耗时 O(V+E)。
    (c) Type-1扩容必增流？True。u∈A 故 s↝u，v∈T 故 v↝t。扩容后 c_f(u,v)>0，
        打通 s↝u→v↝t 完整增广路，由 FF 性质最大流必增加。
    (d) 任意最小割必含Type-2边：由最小割性质，所有最小割源侧 A' 必满足 A⊆A'⊆V\T。
        因 u∈A⊆A'，v∈B\T⊆B'，故 u∈A' 且 v∈B' 恒成立，边 e 必跨越割线。

【复杂度直觉】

  • 正向：BFS/DFS 找 $A, T$ 耗时 $O(V+E)$。理论证明题不考运行代码，考逻辑链。
  • 逆向反推：看到“残量网络/最小割/扩容”必考断连性。牢记口诀：A到B路焊死，s在A出不了墙；Type1通t必增流，Type2死胡同不增。
  • 考场陷阱：证明必须写“满流$\Rightarrow$正向残量0，零流$\Rightarrow$反向残量0$\Rightarrow$G_f无路”。漏写残量映射直接扣逻辑分。

🔹 4. 贪心算法与交换论证 (Exchange Argument)

【识别信号】

  • “调度/排序/优先级/最小化总延迟/最大利润/单核/可抢占/EDF/SRPT”
  • 真题映射：Assign 4 Q1 (SRPT最小化流时间)、Lecture EDF/MST证明。

【直觉类比】
“插队理论”。假设神仙解(OPT)和贪心解(G)第一次选择不同，把神仙解里的顺序强行换成贪心的顺序。算账发现：短任务/早截止任务提前做，总代价只会减少或不变。反复换，神仙解就变成了贪心解，说明贪心本身就是最优。

【数学骨架】

  • 策略描述：明确排序规则或优先队列选择标准（如 SRPT选剩余最短，EDF选截止最早）。
  • 交换论证框架：
    1. 假设 OPT $\neq$ G，设 $t$ 为首次分歧时刻。
    2. G 选 $J_1$（更优指标），OPT 选 $J_2$（较差指标）。
    3. 在 OPT 中交换 $J_1, J_2$ 的执行时段/顺序。
    4. 证明 $\Delta \text{Cost} \le 0$（总代价不增）。
    5. 有限次交换后 OPT $\to$ G，故 G 最优。
      (释义：核心是证明“局部交换不会破坏全局可行性，且目标函数单调不增”。其他任务不受影响，只需分析被交换的两个任务)

【证明模板】

  • 白话逻辑：设OPT在$t$选$J_2$，G选$J_1$（$J_1$剩余更短/截止更早）。将OPT中$J_1$和$J_2$的执行块互换。$J_1$提前完成，代价减少；$J_2$推迟完成，代价增加。但因$J_1$指标更优，减少量 $\ge$ 增加量，总代价不增。其他任务时间窗不变。重复交换消除所有分歧，OPT转化为G且代价未升，故G最优。
  • 数学符号：设分歧点 $t$，$r_1 \le r_2$（SRPT）或 $d_1 \le d_2$（EDF）。交换后完成时间 $C_1' < C_1, C_2' > C_2$。目标函数变化 $\Delta = (C_1'-C_1) + (C_2'-C_2)$。由指标关系可证 $\Delta \le 0$。可行性：交换不改变总占用时长，截止期约束由 $d_1 \le d_2$ 保证互换后仍满足。
  • 考场直接抄写骨架：
    1
    2
    3
    4
    5
    6
    7
    策略：[写明贪心规则，如SRPT/EDF/按利润降序]。
    证明(交换论证)：假设最优解OPT与贪心解G首次在时刻t做出不同选择。
    G选择任务J1(指标更优)，OPT选择J2。在OPT中将J1与J2的执行顺序/时段互换。
    分析影响：其他任务完成时间不变。J1提前完成使代价减少，J2推迟使代价增加。
    由贪心指标性质(J1更优)，减少量≥增加量，总目标函数值不增。
    重复此交换操作可消除所有分歧，将OPT转化为G且代价未升高。
    故贪心解G也是最优解。

【复杂度直觉】

  • 正向：排序 $O(n \log n)$ 或优先队列维护 $O(n \log n)$。模拟执行 $O(n)$ 或 $O(n \log n)$。
  • 逆向反推：看到“最小化总流时间/完成时间” $\to$ SRPT；“满足所有截止期/最小化最大延迟” $\to$ EDF；“区间选最多不重叠” $\to$ 按结束时间早排序。证明必用交换论证，写归纳法通常扣分。
  • 考场陷阱：必须明确写出“交换哪两个任务”和“为什么总代价不增”。漏写 $\Delta \le 0$ 的定量/定性分析扣核心分。可抢占/不可抢占必须看清，策略不同。

🔹 5. 哈夫曼编码与 k 叉推广 (Huffman & k-ary)

【识别信号】

  • “前缀码/数据压缩/频率/合并最小/三进制/k进制/最优编码树”
  • 真题映射：Assign 4 Q5 (Ternary Huffman)、Lecture 二叉哈夫曼。

【直觉类比】
“逆向建树/捆柴火”。频率越小的字符放越深（码长越长）。每次挑最轻的 $k$ 个节点绑在一起，合成一个新父节点往上长。如果叶子数凑不够满 $k$ 叉树，补频率为 0 的虚节点垫底，不增加真实代价但保证结构完整。

【数学骨架】

  • 算法步骤：
    1. 检查叶子数 $n$。若 $(n-1) \mod (k-1) \neq 0$，补 $d = (k-1) - ((n-1)\mod(k-1))$ 个频率为 0 的虚字符。
    2. 建最小堆，插入所有频率。
    3. while 堆大小 > 1: 弹出 $k$ 个最小 $f_1,\dots,f_k$，合并为 $F=\sum f_i$，创建父节点，推回堆。
    4. 返回堆中唯一根节点。
      (释义：每次合并减少 $k-1$ 个节点。要最终剩1个根，必须满足 $(n-1)$ 是 $k-1$ 的倍数。补0频节点不改变 $\sum f_i \cdot depth_i$，但让树能闭合)
  • 代价函数：$L = \sum_{i=1}^n f_i \cdot \text{depth}(i)$。算法最小化 $L$。

【证明模板】

  • 白话逻辑：贪心选择性质+最优子结构。引理：频率最小的 $k$ 个字符在最优树中必为最深兄弟。证明(交换)：若最小频不在最深，与深处节点交换，因频率小换到深处，总代价 $\sum f\cdot d$ 不增。合并后，父节点频率为子和，原问题归约为 $n-k+1$ 个字符的子问题。由归纳法，每步贪心合并保持全局最优。
  • 数学符号：设 $x_1,\dots,x_k$ 为最小频。若最优树 $T$ 中它们非最深兄弟，取最深兄弟 $y_1,\dots,y_k$。交换 $x_i \leftrightarrow y_i$。新代价 $L' = L + \sum (f_{x_i}-f_{y_i})(d_{y}-d_{x}) \le L$（因 $f_x \le f_y, d_y \ge d_x$）。故存在最优树使最小 $k$ 个为最深兄弟。合并后归约，归纳得证。
  • 考场直接抄写骨架：
    1
    2
    3
    4
    5
    6
    7
    算法：若 (n-1)%(k-1)≠0，补频率0的虚字符凑齐。用最小堆维护频率。
    循环弹出k个最小频率节点，合并为父节点(频率为和)，推回堆，直至剩根节点。
    正确性：1.贪心选择性质：频率最小的k个字符在最优树中必为最深兄弟。
    若不然，与深处节点交换，因频率更小，总编码代价 ∑f·d 不会增加。
    2.最优子结构：将k个最小字符合并为父节点后，问题归约为 n-k+1 个字符的
    同类子问题。父节点深度比子节点浅1，代价计算等价。
    由数学归纳法，算法每步贪心合并均保持全局最优性。

【复杂度直觉】

  • 正向：堆操作 $O(\log n)$，合并 $(n-1)/(k-1)$ 次 $\Rightarrow O(n \log n)$。空间 $O(n)$。
  • 逆向反推：考 $k$ 进制必考“补0条件”和“每次合并k个”。证明直接抄二叉模板，把“2”改成“k”，把“最小2个”改成“最小k个”。阅卷只看逻辑框架。
  • 考场陷阱：必须写清补虚节点的公式和原因（保证满k叉树结构）。漏写补0步骤扣5-8分。证明必须分“贪心选择性质”和“最优子结构”两点写。

Part 5: NP完备归约与证明

🔹 1. NP完备证明通用框架（5步标准结构）

【识别信号】

  • 题干要求：Prove NP-complete / Show NP-hard / Decision version
  • 给出 Hint：Hint: Vertex Cover / 3SAT / Subset Sum / Hamiltonian Path
  • 问法特征：是否存在... / 能否找到... / 判断是否可行...（决策问题）

【直觉类比】
“难度传递链”。已知问题 A 是“世界级难题”（NPC）。如果你能把 A 的任意实例，快速翻译成问题 B 的实例，且保证 A有解 ⇔ B有解，那就说明 B 至少和 A 一样难。既然 A 已经难到没有多项式算法，B 也必然没有。这就是归约（Reduction）。

【数学骨架】
标准5步结构（阅卷按点给分，漏一步扣 20%）：

  1. ∈ NP：给定候选解，可在多项式时间内验证合法性与目标。
  2. 归约来源：选择已知 NPC 问题 $A$（优先用 Hint）。
  3. 构造映射：给定 $A$ 的实例 $I$，在多项式时间内构造 $B$ 的实例 $I'$。写明点/边/变量/约束的对应规则。
  4. 正确性 (iff)：
    • $(\Rightarrow)$ 若 $I$ 是 YES，则按构造规则可直接推出 $I'$ 是 YES。
    • $(\Leftarrow)$ 若 $I'$ 是 YES，则按构造逆推可还原出 $I$ 的合法解，故 $I$ 是 YES。
  5. 结论：$A \le_p B$，且 $B \in \text{NP}$，故 $B$ 是 NP-Complete。

【证明模板】（白话逻辑 → 数学符号 → 考场骨架）

  • 白话逻辑：归约不是“解出问题”，而是“搭建桥梁”。构造过程只是画点画边/列不等式，显然很快（多项式时间）。双向证明的核心是“结构保真”：原问题的每个约束都被新问题的结构锁死，新问题的每个合法解都能无损翻译回原问题。
  • 数学符号：设映射函数 $f: I_A \to I_B$。证明 $T(f) = O(n^c)$，且 $I_A \in \text{YES} \iff f(I_A) \in \text{YES}$。由 NPC 定义，若 $A$ 是 NPC 且 $A \le_p B$，则 $B$ 是 NP-Hard。结合 $B \in \text{NP}$，得 $B$ 是 NPC。
  • 考场直接抄写骨架：
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    1. ∈NP：给定候选解S，可在O(n^c)时间内验证S是否满足所有约束且达到目标值。故∈NP。
    2. 归约来源：从[Hint给的NPC问题]归约。
    3. 构造映射：给定[已知问题]实例I，构造本题实例I'：
       - 元素映射：...
       - 约束映射：...
       - 参数设置：...
       构造仅涉及建点/建边/列不等式，耗时O(n^c)，为多项式时间。
    4. 正确性(iff)：
       (⇒) 若I有解，按映射规则直接构造I'的解，验证满足所有约束，故I'为YES。
       (⇐) 若I'有解，由构造的结构限制，该解必对应I的一个合法赋值/选择，逆推得I为YES。
    5. 结论：已知NPC ≤p 本题，且本题∈NP，故本题为NP-Complete。✅

【复杂度直觉】

  • 归约本身不要求解出问题，只要求构造过程是多项式时间 $O(n^c)$。
  • 致命陷阱：归约方向永远是 已知NPC ≤p 本题。写反（本题≤p已知）直接 0 分。
  • 考场若构造细节卡住：写清映射意图 + iff 框架 + “构造显然多项式时间”，可拿 60% 步骤分。绝不空题。

🔹 2. 核心 NPC 问题字典（考场现读指南）

💡 使用说明：考试遇到 NP 证明题，先扫题干特征词，对照下表锁定“归约源问题”。每个问题提供 直觉/它在问什么、形式化定义、映射技巧、考场速记。现读完全足够。

🔸 3SAT (布尔可满足性)

  • 它在问什么/直觉：给你一堆逻辑子句，每句是 3 个变量的 OR（如 $x_1 \lor \neg x_2 \lor x_3$）。问能否给每个变量赋 True/False，让所有子句同时为真？本质是“多条件同时满足的开关配置”。
  • 形式化定义：给定 3CNF 公式 $\phi$（$m$ 个子句，$n$ 个变量），问是否存在真值赋值使 $\phi$ 为真。
  • 核心特征词：布尔变量 / 真假赋值 / 子句 / 逻辑与或 / 满足 / 冲突
  • 归约映射技巧：
    • 变量 $x_i$ → 二选一结构（路径方向/颜色/0-1整数/选边）
    • 子句 $(l_1 \lor l_2 \lor l_3)$ → “至少一个成立”约束（容量≤2/团节点/独立集补）
    • $\neg x_i$ → 反向选择/互补变量
  • 考场速记：看到“逻辑/真假/子句/至少一个满足” → 必从 3SAT 归约。映射核心：变量→二选一，子句→至少一真。

🔸 Vertex Cover (VC, 顶点覆盖)

  • 它在问什么/直觉：给一张图，问能否选 ≤k 个顶点，使得每条边至少有一个端点被选中？本质是“用最少的监控摄像头覆盖所有走廊”。
  • 形式化定义：给定图 $G=(V,E)$ 和整数 $k$，问是否存在 $C \subseteq V, |C| \le k$，使 $\forall (u,v)\in E, u\in C \lor v\in C$。
  • 核心特征词：选点覆盖边 / 预算k / 每条边至少一端 / 资源分配覆盖
  • 归约映射技巧：
    • 边 → 约束/任务/子集
    • 顶点 → 资源/决策/元素
    • 预算 k → 容量/数量上限
  • 考场速记：看到“选最少点覆盖所有约束/边/任务” → 从 VC 归约。与 IS/Clique 互补。Assign 5 Q1(Hitting Set)、Q3(Steiner Tree) 均从 VC 归约。

🔸 Independent Set (IS, 独立集)

  • 它在问什么/直觉：给一张图，问能否选 ≥k 个顶点，使得任意两点之间都没有边？本质是“挑一堆互不冲突的人/任务”。
  • 形式化定义：给定图 $G=(V,E)$ 和整数 $k$，问是否存在 $S \subseteq V, |S| \ge k$，使 $\forall u,v \in S, (u,v) \notin E$。
  • 核心特征词：互不相连 / 无冲突 / 独立 / 不相邻 / 最多选k个互斥项
  • 归约映射技巧：
    • 顶点 → 物品/任务/选项
    • 边 → 冲突/互斥/不能同时选
    • 互补定理：$S$ 是 IS $\iff V \setminus S$ 是 VC。故 $G$ 有大小 $k$ 的 IS $\iff G$ 有大小 $n-k$ 的 VC。
  • 考场速记：看到“选一堆互不干扰的元素” → 从 IS 归约（或 VC 补集）。Final Q5(圆桌座位) 本质是 IS/HC 变种。

🔸 Clique (团)

  • 它在问什么/直觉：给一张图，问能否选 ≥k 个顶点，使得任意两点之间都有边（构成完全子图）？本质是“找一个内部全认识的小圈子”。
  • 形式化定义：给定图 $G=(V,E)$ 和整数 $k$，问是否存在 $K \subseteq V, |K| \ge k$，使 $\forall u,v \in K, (u,v) \in E$。
  • 核心特征词：两两相连 / 完全子图 / 内部全兼容 / 团
  • 归约映射技巧：
    • 补图转换：$G$ 有大小 $k$ 的 Clique $\iff \bar{G}$（补图）有大小 $k$ 的 IS。
    • 3SAT归约：每个子句建3个点，同子句不连边，矛盾变量不连边，找 $m$-团等价于每句选一真literal。
  • 考场速记：看到“两两兼容/全连接/内部无冲突” → 从 Clique 归约。常与 IS 通过补图互换。

🔸 Hamiltonian Path / Cycle (HP/HC, 哈密顿路径/环)

  • 它在问什么/直觉：给一张图，问是否存在一条简单路径/环，恰好经过每个顶点一次？本质是“不重复不遗漏地遍历所有城市”。
  • 形式化定义：给定图 $G=(V,E)$，问是否存在简单路径/环覆盖 $V$ 中所有顶点。
  • 核心特征词：遍历所有点 / 恰好一次 / 不重复 / 简单路径/环 / 一笔画
  • 归约映射技巧：
    • 顶点 → 城市/步骤/必须访问的节点
    • 边 → 允许的移动/顺序
    • 长度限制 → 恰好 $n-1$ 条边（路径）或 $n$ 条边（环）
  • 考场速记：看到“经过所有点恰好一次/固定长度简单环” → 从 HP/HC 归约。Assign 5 Q4(Zero-Weight Cycle) 令 $K=n-1$ 即一步归约。

🔸 Subset Sum (子集和)

  • 它在问什么/直觉：给你一堆正整数和一个目标值 $B$，问能否挑出几个数，让它们加起来恰好等于 B？本质是“凑金额/拼长度”。
  • 形式化定义：给定正整数集 ${a_1,\dots,a_n}$ 和目标 $B$，问是否存在 $I \subseteq {1,\dots,n}$ 使 $\sum_{i\in I} a_i = B$。
  • 核心特征词：凑和 / 恰好等于 / 选或不选 / 数字权重 / 目标值
  • 归约映射技巧：
    • 数字 $a_i$ → 边权/路径长/物品重量/时间片
    • 目标和 $B$ → 容量/环权/截止时间/回边负权
    • 选/不选 → 路径分叉/0-1变量
  • 考场速记：看到“选若干元素凑精确值/路径和恰好K” → 从 Subset Sum 归约。映射核心：数字→权重，和→目标，选→分叉。

🔸 Partition (划分)

  • 它在问什么/直觉：给你一堆数，问能否分成两组，使两组的和完全相等？本质是“平分负载/天平平衡”。
  • 形式化定义：给定正整数集 $S$，问是否存在 $S_1 \subseteq S$ 使 $\sum_{x\in S_1} x = \sum_{x\in S\setminus S_1} x = \frac{1}{2}\sum S$。
  • 核心特征词：平分 / 两组和相等 / 负载均衡 / 对半切
  • 归约映射技巧：
    • 是 Subset Sum 的特例（$B = \frac{1}{2}\sum S$）。
    • 映射到调度：2台机器，Makespan ≤ T $\iff$ Partition 可行。
  • 考场速记：看到“平分/两组/负载均衡/2台机器最小化最大完成时间” → 从 Partition 归约。

🔸 Set Cover / Hitting Set (集合覆盖/击中集)

  • 它在问什么/直觉：
    • Set Cover：给一堆子集，选最少子集覆盖全集。
    • Hitting Set：给一堆子集，选最少元素，让每个子集至少包含一个选中元素。
    • 本质是“用最少的钥匙打开所有的锁”。
  • 形式化定义：Hitting Set：给定全集 $A$，子集族 ${S_1,\dots,S_m}$，预算 $b$。问是否存在 $H \subseteq A, |H| \le b$，使 $\forall i, H \cap S_i \neq \emptyset$。
  • 核心特征词：击中/覆盖所有子集 / 预算b / 每个约束至少满足一个
  • 归约映射技巧：
    • VC 是 Hitting Set 的特例：边 $e={u,v}$ 就是二元子集 $S_e={u,v}$。覆盖边 = 击中子集。
    • 元素 → 顶点/决策，子集 → 边/约束。
  • 考场速记：看到“选元素击中/覆盖所有子集/约束” → 从 VC 或 Set Cover 归约。Assign 5 Q1 直接考此映射。

🔹 3. 归约映射技巧库（考场翻译表）

💡 遇到新题，对照此表把“业务语言”翻译成“图论/逻辑/数学语言”。

原题业务约束 翻译为目标问题的结构 典型应用
变量 True/False 0/1整数、节点红蓝染色、路径左/右走向、选边/不选边 3SAT→整数规划/2-Color/HP
逻辑 OR (至少一个真) 容量限制≤2、团中必选1点、独立集补、子句约束和≤2 3SAT→Clique/IntegerProg
冲突/互斥/不能同时 图边连接、颜色不同、独立集约束、补图边 IS/2-Color/调度冲突
求和/凑精确值 边权累加、路径总长、背包重量、回边负权抵消 SubsetSum→ZeroWeightCycle
遍历所有/恰好一次 哈密顿路径、简单环长度=n-1、DAG拓扑覆盖 HP/HC→TSP/路径规划
覆盖所有边/约束 顶点覆盖、击中集、集合覆盖、流满流判定 VC→HittingSet/SteinerTree
预算/数量上限 k 割容量、背包容量、流限制、独立集/团大小 通用参数映射

🔹 4. 考场现读与构造策略（不会写也能抢分）

【如何考场现读 NPC 题目】

  1. 圈特征词：扫描题干，找 覆盖/独立/真假/凑和/遍历/平分/击中。
  2. 查字典：对照 Part 5.2 锁定 1 个源问题（Hint 给谁就用谁，90% 情况）。
  3. 找映射：问自己“原题的‘物品’对应源问题的什么？原题的‘限制’对应源问题的什么？”
  4. 搭骨架：直接套 5 步模板。构造细节写不出，就写“将源问题的X映射为本题的Y，约束Z映射为容量/边/不等式W”。
  5. 写 iff：$(\Rightarrow)$ 按映射拼装；$(\Leftarrow)$ 按结构逆推。强调“构造仅建点建边，多项式时间”。

【构造卡壳时的保底写法】

1
2
3
4
5
6
7
8
3. 构造映射：给定[源问题]实例I，构造本题实例I'。
   将源问题的[变量/元素]映射为本题的[节点/整数/路径]；
   将源问题的[约束/子句/边]映射为本题的[容量限制/不等式/图边]；
   参数k/B映射为本题的[预算/目标值/回边权]。
   构造仅涉及O(n^c)次建点/建边/列式，为多项式时间。
4. 正确性：
   (⇒) 若I有解，按上述映射直接构造I'的合法解，满足所有约束。
   (⇐) 若I'有解，由构造的硬约束限制，该解必唯一对应I的一个合法赋值，逆推得I有解。

阅卷视角：只要映射意图清晰、iff 结构完整、方向正确、声明多项式时间，即使具体边权/不等式写错，也能拿 15/25 分。

🔹 5. 复杂度直觉 & 考场避坑清单

致命陷阱 正确做法 扣分后果
归约方向写反 永远 已知NPC ≤p 本题（Hint给谁就从谁出发） 直接 0 分
漏写 ∈NP 第一句必写“给定解可多项式时间验证” 扣 3-5 分
iff 只写单向 必须分 $(\Rightarrow)$ 和 $(\Leftarrow)$ 两段 扣 8-10 分
没提多项式时间 构造后补一句“显然可在 O(n^c) 完成” 扣 3 分
把优化问题当决策 NP只证决策版（“是否存在≤k/≥B”） 逻辑不严谨扣 2-3 分
死磕完美构造 写清映射意图+iff框架+多项式声明 → 拿保底分 空题 0 分，写框架 60%

【考场时间分配建议】

  • 前 3 分钟：圈特征词 → 查字典 → 定源问题。
  • 第 4-8 分钟：默写 5 步骨架 → 填 ∈NP 和归约来源。
  • 第 9-15 分钟：写构造映射（点/边/参数对应）→ 写 iff 双向逻辑。
  • 第 16-20 分钟：补多项式时间声明 → 检查方向 → 写结论。
  • 绝不空卷。框架写满 > 细节完美。

快来参与讨论吧~