算法设计范式与动态规划

13.1 算法设计范式总览：六把锤子

13.1.1 什么是「算法设计范式」

学到现在，你手里已经攒了不少算法：二分查找、快速排序、KMP、Dijkstra、哈希……但它们是具体问题的具体解法。 真正让你在考场上、在工程里能举一反三的，是它们背后共用的那几条思维套路。这种「跨问题复用的高层解题策略」， 我们称为算法设计范式（algorithm design paradigm）。

范式不是算法，它不给你代码，只给你思考的方向。举例来说： 「枚举所有可能性，逐一检查」是暴力法； 「把问题切成两半分别解决再合起来」是分治； 「每一步都选当前看起来最好的，并且敢打包票最终一定最好」是贪心； 「枚举所有可能性，但走一步看一步，走不通就退回来」是回溯； 「枚举所有可能性，但把重复出现的子问题答案记下来，以后直接查表」是动态规划。

你会发现这六种范式的核心矛盾始终是同一个：解空间太大了，怎么才能不把所有可能都试一遍？ 暴力法与回溯法是「傻试」与「聪明地试」，分治与贪心是「按结构拆」与「按局部拍板」， 动态规划则是「按阶段拆 + 去冗余」。理解了这条主线，六个范式就不再是六块孤立的石头。

13.1.2 六个范式的一句话本质与代价

暴力枚举 Brute Force

把解空间全部枚举一遍，逐个验证。它是所有算法的基准线（baseline）， 也是你在考场上想不出正解时的保底分。代价：解空间通常是 O(2ⁿ) 或 O(n!)，n 稍微大一点就爆。

分治 Divide and Conquer

把大问题划分成若干规模更小的同类子问题，递归求解后合并。 关键在于子问题互相独立、不重叠——一旦重叠，分治就会重复计算，此时应该换成 DP。 复杂度由主定理给出，常见形态 T(n) = 2T(n/2) + O(n) = O(n log n)。

贪心 Greedy

每一步都做当前看起来最优的选择，并且永不反悔。 它快得离谱（往往是 O(n log n) 的排序加一趟扫描），但正确性必须证明—— 证明不了，就说明这题不能用贪心。它的合法性建立在两个性质上：贪心选择性质与最优子结构。

回溯 Backtracking

把问题的求解过程看成一棵解空间树的深度优先遍历：每走一步做一个决策， 发现当前分支已经不可能产生合法解（约束函数）或不可能更优（限界函数）时，就撤销这一步、退回上一层再试别的选择。 一句话：回溯 = DFS + 剪枝。它能求出全部可行解（或最优解），最坏复杂度仍然是指数级，但剪枝好时实际运行快很多。

动态规划 Dynamic Programming

把问题拆成有先后顺序的阶段，为每个阶段定义状态， 写出状态之间的转移方程，然后自底向上把所有状态的答案算一遍存进表里。 它比回溯聪明的唯一原因：重叠子问题只算一次，把指数级的重复劳动压成了多项式级。 一句话：DP = 回溯 + 记忆化 + 去掉冗余状态。

分支限界 Branch and Bound

回溯是深度优先「一条道走到黑」，分支限界则是广度优先 / 优先队列地扩展结点， 每次挑「最有希望」的那个（例如当前价值上界最大的）去展开，一旦某结点的上界都不如已知的最好解，就整枝砍掉。 它适合求最优解（而不是全部解），典型应用是 0-1 背包、TSP、作业分配。

13.1.3 六范式对照表：先记住这张表

这张表建议直接背下来。考试里遇到「下列问题应该用哪种算法设计策略」这类题，考的就是它。

13.1.4 选范式的思考流程

拿到一道题，不要急着写代码，先按下面的顺序问自己四个问题。这个流程会一直用到本章结束。

1. 解空间有多大？如果能承受 2ⁿ（n ≤ 20）或 n!（n ≤ 10）， 直接用回溯甚至暴力，把时间花在写对代码上。如果 n 到了 1000 以上，就必须是多项式算法。
2. 子问题是否重叠？画一下递归树。如果同一个子问题（例如 f(3,5)）在树里出现了两次以上， 说明有重叠子问题——分治立刻出局，改上 DP 或记忆化搜索。
3. 每步能不能拍板？如果每一层都能选出一个「明显不亏」的局部最优，并且你能证明它不后悔， 那就是贪心，能拿到最快的复杂度。证明不出来就退回 DP，别硬猜。
4. 阶段能否划分？能不能把问题按「前 i 个物品」「前 i 个字符」「区间 [l, r]」「已访问集合 S」这样的维度 组织成有序的阶段？如果能，DP 的状态设计就有眉目了。

13.1.5 互动演示：六个范式的决策路径

下面这个动画把「拿到一道题，该怎么一步步选出合适的范式」画成了流程图。 点击播放或单步，跟着高亮走一遍这条决策链：

13.2 回溯法与解空间树

13.2.1 解空间树：把「枚举」画成一棵树

回溯法（backtracking）的思想非常朴素：把求解过程看成一系列决策，每个决策有若干种选择， 所有决策串起来就形成一棵树，我们在这棵树上做深度优先搜索。这棵树叫解空间树（solution space tree）， 树上从根到叶的一条路径就是一个候选解，叶子的总数就是解空间的规模。

同一个问题的解空间树可以有不同的组织方式，最常见的有两种：

子集树 Subset Tree

每一层对「第 i 个元素」做选 / 不选的二元决策，树是一棵二叉树， 深度为 n，叶子数 2ⁿ，总结点数 2ⁿ⁺¹ − 1。 典型问题：0-1 背包、子集和、装载问题、图的着色（每个顶点选一种颜色时它其实是 m 叉的推广）。
时间复杂度：Ω(2ⁿ)。

排列树 Permutation Tree

每一层确定「第 i 个位置放哪个还没用过的元素」，第一层有 n 种选择，第二层 n−1 种……， 叶子数 n!。典型问题：全排列、TSP（旅行商）、N 皇后（如果按行放置，则第 i 行选一个列号， 由于列不能重复，它正是一棵排列树的变体）。
时间复杂度：Ω(n!)。

13.2.2 回溯法的两套框架代码

解空间树的遍历方式不同，回溯法的写法也有两套。递归回溯写起来短、可读性好， 是竞赛与工程中的主流；迭代回溯用循环加显式栈模拟，避免了递归的函数调用开销， 也是考研大纲里要求会写的形式。两套模板都要能默写。

#include <iostream>
#include <vector>
using namespace std;

/* ============================================================
   回溯法模板（通用骨架）—— 以"从 n 个数中选若干"为例
   递归回溯：把解空间树的一层对应一次递归调用
   ============================================================ */
const int MAXN = 100;
int n = 5;                 // 元素个数
int x[MAXN];               // 解向量：x[t] 表示第 t 层做的决策
long long nodeCount = 0;   // 搜索过的结点数（用于对比剪枝效果）

/* 约束函数 constraint(t)：判断第 t 层取 x[t] 是否合法
   例：这里要求"不能连续两次选同一种决策"，真实题目请替换成自己的约束 */
bool constraint(int t) {
    if (t >= 2 && x[t] == x[t - 1]) return false;
    return true;
}

/* 限界函数 bound(t)：判断当前部分解还有没有希望超过已知最优
   例：这里要求"最多只能选 3 个 1"，超过就直接砍掉 */
int selectedSoFar(int t) {
    int c = 0;
    for (int i = 1; i <= t; ++i) if (x[i] == 1) ++c;
    return c;
}
bool bound(int t) {
    return selectedSoFar(t) <= 3;
}

/* 到达叶子：得到一个完整可行解 */
void output(int depth) {
    cout << "解：";
    for (int i = 1; i <= depth; ++i) cout << x[i] << ' ';
    cout << "\n";
}

void backtrack(int t) {
    ++nodeCount;
    if (t > n) {                       /* 到达第 n+1 层 = 叶子，得到一个完整解 */
        output(n);
        return;
    }
    for (int choice = 0; choice <= 1; ++choice) {   /* 第 t 层有 2 种选择 */
        x[t] = choice;                              /* ① 做选择 */
        if (constraint(t) && bound(t)) {            /* ② 剪枝：约束函数 + 限界函数 */
            backtrack(t + 1);                       /* ③ 进入下一层 */
        }
        /* ④ 撤销选择：x[t] 会在下一轮循环被覆盖，显式写出来是为了对称与清晰 */
        x[t] = 0;
    }
}

int main() {
    backtrack(1);
    cout << "搜索结点数 = " << nodeCount << "\n";
    return 0;
}

#include <iostream>
using namespace std;

/* ============================================================
   迭代回溯模板：显式维护层号 t 与解向量 x[]
   适用于"每层有 m 种选择"的一般解空间树（本例子集树 m = 2）
   ============================================================ */
const int MAXN = 100;
int n = 4, m = 2;          // n 层，每层 m 种选择
int x[MAXN];               // x[t] 的取值 0..m-1，初始 -1 表示"还没试过任何选择"
long long nodeCount = 0;

bool constraint(int t) {
    // 这里放具体的约束函数；本例约束：奇偶交替（只是演示）
    return true;
}

int main() {
    for (int i = 1; i <= n + 1; ++i) x[i] = -1;   // 全部置为"未选择"

    int t = 1;                                    // 从第 1 层开始
    while (t >= 1) {
        ++nodeCount;
        x[t] = x[t] + 1;                          // 试下一种选择
        while (x[t] < m && !constraint(t)) x[t]++;  // 跳过所有不合法的选择

        if (x[t] < m) {                           // 找到了一种合法选择
            if (t == n) {                         // 已经到最后一层 → 得到一个解
                cout << "解：";
                for (int i = 1; i <= n; ++i) cout << x[i] << ' ';
                cout << "\n";
                /* 注意：这里不 t++，而是继续 for 循环给 x[t] 换下一个取值，
                   从而枚举同一层的其余兄弟结点 */
            } else {
                ++t;                              // 深入下一层
                x[t] = -1;                        // 新层从"未选择"开始
            }
        } else {
            x[t] = -1;                            // 本层所有选择都试完了
            --t;                                  // 回溯到上一层
        }
    }
    cout << "搜索结点数 = " << nodeCount << "\n";
    return 0;
}

13.2.3 剪枝：约束函数与限界函数

回溯法之所以比暴力枚举快，全靠剪枝（pruning）。剪枝分成两类，考的、用的都是这两个名字：

约束函数 Constraint Function

判断「当前的部分解是否满足问题的硬性约束」。不满足就直接砍掉整棵子树， 因为再怎么往下走也还是非法解。
例：N 皇后中「新放的皇后不能与已放的皇后同列、同对角线」；图着色中「相邻顶点不能同色」； 子集和中「当前和已经超过目标值」。

限界函数 Bound Function

判断「当前的部分解还有没有可能比已知的最优解更好」。如果即使剩下的选择全都做到最好， 也超不过当前最优，就砍掉。它只用于求最优解的问题，且必须保证「估计值不会低估」—— 估计错了会把最优解剪掉，这是最危险的 bug。
例：0-1 背包回溯中「当前价值 + 剩余物品全部装下的价值上界 ≤ 目前最优值 → 剪枝」。

13.2.4 经典案例①：N 皇后

问题：在 n × n 的棋盘上放 n 个皇后，使得任意两个皇后都不在同一行、同一列、同一条斜线上。 求所有摆法（或摆法总数）。

本质：既然每行必须恰好放一个皇后，那就按行放置：第 i 行选一个列号 x[i]， 于是解向量是 (x[1], x[2], …, x[n])，解空间是一棵排列树的变体—— 如果再加「列不能重复」的约束，它正好退化成 n! 个叶子的排列树。

约束函数（判断在第 t 行第 j 列放皇后是否合法）： ① 第 j 列没有皇后；② 主对角线（左上到右下，编号 i − j，加偏移量 n 变成正数）没有皇后； ③ 副对角线（右上到左下，编号 i + j）没有皇后。 用三个布尔数组把判断降到 O(1)，这是 N 皇后能秒出解的关键。

先看下面这个动画：它以 4 皇后为例，把「试探 → 冲突 → 回溯 → 找到解」的全过程逐帧画出来。 注意观察右侧三个布尔数组是怎么被标记与撤销的，以及递归深度如何随回溯下降。

#include <iostream>
#include <vector>
#include <string>
using namespace std;

/* ============================================================
   N 皇后（回溯法，按行放置 + O(1) 冲突判定）
   col[j]      第 j 列是否已有皇后
   dg[i-j+n]   主对角线（左上→右下，i-j 相同）是否已有皇后
   udg[i+j]    副对角线（右上→左下，i+j 相同）是否已有皇后
   ============================================================ */
int n;
vector<int> x;                 // x[i] = 第 i 行皇后所在的列（1..n）
vector<bool> col, dg, udg;
long long solutions = 0;        // 解的总数
long long nodes = 0;            // 搜索结点数（衡量剪枝效果）

void dfs(int i) {
    ++nodes;
    if (i > n) {                            // 第 n+1 行：n 个皇后都放好了
        ++solutions;
        if (solutions <= 3) {               // 只打印前 3 个解，避免刷屏
            cout << "解 " << solutions << "：";
            for (int r = 1; r <= n; ++r) cout << x[r] << " \n"[r == n];
        }
        return;
    }
    for (int j = 1; j <= n; ++j) {          // 第 i 行尝试每一列
        if (col[j] || dg[i - j + n] || udg[i + j]) continue;   // 约束函数：O(1) 判冲突

        x[i] = j;                            /* ① 做选择 */
        col[j] = dg[i - j + n] = udg[i + j] = true;

        dfs(i + 1);                          /* ② 递归下一行 */

        col[j] = dg[i - j + n] = udg[i + j] = false;   /* ③ 撤销选择（回溯） */
    }
}

int main() {
    n = 8;
    x.assign(n + 1, 0);
    col.assign(n + 1, false);
    dg.assign(2 * n + 2, false);
    udg.assign(2 * n + 2, false);

    dfs(1);
    cout << n << " 皇后共有 " << solutions << " 个解，搜索结点数 = " << nodes << "\n";
    /* 8 皇后输出：92 个解，搜索结点数约 2057（远小于 8! = 40320 与 8^8 = 16777216） */
    return 0;
}

13.2.5 经典案例②：迷宫求解（与第 03 讲栈实现对照）

第 03 讲我们学过「用栈求解迷宫问题」：从入口出发，把走过的格子压栈，遇到死路就弹栈退回上一个格子。 现在再看它，你会发现——那就是一次手写的迭代回溯。

解空间树：每个格子最多有 4 个分支（上下左右），树的分支因子 ≤ 4，深度最大为 m×n， 所以最坏复杂度 O(4^(m·n))（实际因为不能走回头路，远小于这个上界）。 约束函数：① 在迷宫范围内；② 不是墙；③ 没有走过（否则会死循环）。

#include <iostream>
#include <vector>
using namespace std;

/* ============================================================
   迷宫求解：递归回溯（DFS）
   与第 03 讲的"栈 + 迭代"版本对照：
     栈版本的 push = 这里的"做选择"，pop = 这里的"撤销选择"
   ============================================================ */
int m = 5, n = 5;
int maze[5][5] = {
    {0, 1, 0, 0, 0},
    {0, 1, 0, 1, 0},
    {0, 0, 0, 1, 0},
    {0, 1, 1, 1, 0},
    {0, 0, 0, 0, 0}
};                              // 0 = 通路，1 = 墙
bool vis[5][5];
vector<pair<int,int>> path;      // 当前路径（即"栈"）
long long nodes = 0;
bool found = false;

int dx[4] = {-1, 1, 0, 0};      // 上 下 左 右
int dy[4] = {0, 0, -1, 1};

/* 约束函数：越界 / 是墙 / 已访问 都不合法 */
bool ok(int x, int y) {
    return x >= 0 && x < m && y >= 0 && y < n && maze[x][y] == 0 && !vis[x][y];
}

void dfs(int x, int y) {
    ++nodes;
    vis[x][y] = true;                 /* ① 做选择：进入 (x,y) */
    path.push_back({x, y});           /*    等价于栈版本的 push */

    if (x == m - 1 && y == n - 1) {   /* 到达出口 */
        found = true;
        cout << "找到一条路径，长度 " << path.size() << "：";
        for (size_t k = 0; k < path.size(); ++k)
            cout << "(" << path[k].first << "," << path[k].second << ")" << (k + 1 == path.size() ? "\n" : " -> ");
        /* 注意：这里不 return，继续搜索可以找出所有路径；
           若只想要一条路径，此处 return 即可（但别忘了恢复现场）。 */
    }

    for (int d = 0; d < 4; ++d) {
        int nx = x + dx[d], ny = y + dy[d];
        if (ok(nx, ny)) dfs(nx, ny);  /* ② 递归深入 */
    }

    path.pop_back();                  /* ③ 撤销选择：等价于栈版本的 pop */
    vis[x][y] = false;                /*    注意：求"所有路径"必须恢复 vis；
                                         若只求"是否存在通路"，可以不恢复（相当于剪枝） */
}

int main() {
    dfs(0, 0);
    cout << (found ? "存在通路" : "不存在通路") << "，共访问 " << nodes << " 个状态\n";
    return 0;
}

13.2.6 经典案例③：子集和与 0-1 背包的回溯解法

这两个问题是同一棵子集树上的两种剪枝方式，放在一起讲最清楚。

子集和问题：给定 n 个正整数与目标值 C，问是否存在一个子集，元素之和恰好为 C（或求方案数）。 解空间树是子集树，约束函数：cw + w[i] <= C（当前和加上待选的已经超了，就没必要选）； 限界函数：cw + remain >= C（剩下的全加起来都到不了 C，就没必要继续）。 这两个方向一夹，搜索量能砍掉一大半。

0-1 背包的回溯解法：物品不可分割，每件选或不选，同样是子集树。 约束函数：cw + w[i] <= V（装不下就别装）； 限界函数：把「剩余物品按单位价值从高到低、可以切开装」的分数背包解作为上界 ——这是松弛（relaxation）思想：把难问题放松成容易的问题，用容易问题的最优值当界。 因为分数背包的最优值 ≥ 0-1 背包的最优值，所以这个上界永不高估（不会误杀最优解）。

#include <iostream>
#include <vector>
using namespace std;

/* ============================================================
   子集和问题（回溯法，子集树）
   给定 n 个正整数与目标 C，输出所有和为 C 的子集
   剪枝 1（约束）：cw + w[i] > C 则不选
   剪枝 2（限界）：cw + 剩余全部之和 < C 则整枝砍掉
   ============================================================ */
int n = 6, C = 10;
int w[7] = {0, 1, 2, 3, 4, 5, 6};     // 下标从 1 开始，方便阅读
int x[7];                              // x[i] = 1 表示选第 i 个数
int cw = 0;                            // 当前和
long long nodes = 0, solCount = 0;

void dfs(int i, int rest) {            // rest = 第 i..n 个数的总和（预处理出来更好）
    ++nodes;
    if (cw == C) {                     // 找到一组解（不必等到叶子，可提前输出）
        ++solCount;
        cout << "解 " << solCount << "：";
        for (int k = 1; k <= n; ++k) if (x[k]) cout << w[k] << ' ';
        cout << "\n";
        return;                        // 都是正整数，再往下加只会超过 C
    }
    if (i > n) return;

    /* 剪枝 2：剩下的全加上也到不了 C，整枝砍掉 */
    if (cw + rest < C) return;

    /* 分支 1：选第 i 个数 */
    if (cw + w[i] <= C) {              /* 剪枝 1：约束函数 */
        x[i] = 1; cw += w[i];
        dfs(i + 1, rest - w[i]);
        cw -= w[i]; x[i] = 0;          /* 撤销选择 */
    }
    /* 分支 2：不选第 i 个数 */
    x[i] = 0;
    dfs(i + 1, rest - w[i]);
}

int main() {
    int total = 0;
    for (int i = 1; i <= n; ++i) total += w[i];
    dfs(1, total);
    cout << "共 " << solCount << " 组解，搜索结点数 = " << nodes << "\n";
    /* 输出：{1,2,3,4} / {1,3,6} / {1,4,5} / {2,3,5} / {4,6} —— 共 5 组 */
    return 0;
}

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

/* ============================================================
   0-1 背包 · 回溯法（含限界函数 bound）
   与 13.5.3 的动态规划解法对照：本解法最坏 O(2^n)，但加界后实际很快
   ============================================================ */
struct Item { int w, v; };
int n = 4, V = 7;
Item it[5] = {{0,0}, {3,9}, {4,10}, {5,12}, {2,4}};   // 下标 1..n
int x[5], bestX[5];
int cw = 0, cp = 0, bestp = 0;
long long nodes = 0;

bool cmp(const Item& a, const Item& b) {        // 按单位价值降序，让界更紧、剪枝更狠
    return (double)a.v / a.w > (double)b.v / b.w;
}

/* 限界函数：把第 i..n 件物品按"可以切开"（分数背包）估计一个价值上界。
   分数背包的解一定 >= 0-1 背包的解，所以它是安全的上界（不会低估）。 */
double bound(int i) {
    double rw = V - cw, rv = cp;
    for (int k = i; k <= n && rw > 0; ++k) {
        if (it[k].w <= rw) { rw -= it[k].w; rv += it[k].v; }        // 整件装下
        else { rv += (double)it[k].v / it[k].w * rw; rw = 0; }      // 装一部分
    }
    return rv;
}

void dfs(int i) {
    ++nodes;
    if (i > n) {                                  // 到达叶子
        if (cp > bestp) {
            bestp = cp;
            for (int k = 1; k <= n; ++k) bestX[k] = x[k];
        }
        return;
    }

    /* 分支 1：选第 i 件 —— 先判约束函数，再判限界函数 */
    if (cw + it[i].w <= V) {                      /* 约束：装得下 */
        x[i] = 1; cw += it[i].w; cp += it[i].v;
        if (bound(i + 1) > bestp) dfs(i + 1);     /* 限界：还有希望更优才深入 */
        cw -= it[i].w; cp -= it[i].v; x[i] = 0;   /* 撤销 */
    }

    /* 分支 2：不选第 i 件 */
    x[i] = 0;
    if (bound(i + 1) > bestp) dfs(i + 1);
}

int main() {
    sort(it + 1, it + n + 1, cmp);
    bestp = 0;
    dfs(1);
    cout << "最优价值 = " << bestp << "　选取：";
    for (int k = 1; k <= n; ++k) if (bestX[k]) cout << "(" << it[k].w << "," << it[k].v << ") ";
    cout << "\n搜索结点数 = " << nodes << "（不剪枝要访问 2^" << n << " = " << (1 << n) << " 量级的结点）\n";
    /* 物品 (3,9)(4,10)(5,12)(2,4)，容量 7：最优选 (2,4)+(5,12) = 16，或 (3,9)+(2,4)=13… 
       遍历可知最优为 16；这就是"贪心会错、必须搜索或 DP"的实例。 */
    return 0;
}

13.2.7 经典案例④：图的 m 着色问题

问题：给定无向连通图 G = (V, E) 和 m 种颜色，为每个顶点染一种颜色， 使任意一条边的两个端点颜色不同。求所有染色方案数（或最少需要几种颜色，即色数 chromatic number）。

解空间树：第 i 层为第 i 个顶点选颜色，每层有 m 种选择，树是一棵完全 m 叉树， 叶子数 mⁿ。约束函数：顶点 i 的颜色不能与任何已染色且相邻的顶点相同。 注意回溯法求的是「m 着色方案数」，而求「最少颜色数」需要从小到大枚举 m 逐一判断，或者用分支限界/贪心近似。

这个问题在工程里对应的是寄存器分配（把变量看作顶点、冲突看作边，颜色数 = 可用寄存器数）、 地图染色（四色定理）、考试时间表排课（同一位老师的两门课不能同一时段）。

#include <iostream>
#include <vector>
using namespace std;

/* ============================================================
   图的 m 着色问题（回溯法，完全 m 叉解空间树）
   求：给 n 个顶点染 m 种颜色、相邻顶点异色的所有方案数
   ============================================================ */
int n = 5, m = 3;                                  // 5 个顶点，3 种颜色
int g[6][6] = {0};                                 // 邻接矩阵，下标 1..n
vector<int> color;                                 // color[i] ∈ [1, m]
long long schemes = 0, nodes = 0;

/* 约束函数：顶点 t 染成 c 是否与已染色邻居冲突 */
bool ok(int t, int c) {
    for (int k = 1; k < t; ++k)
        if (g[t][k] && color[k] == c) return false;   // 邻居已用同色 → 非法
    return true;
}

void dfs(int t) {
    ++nodes;
    if (t > n) {                                    // 全部顶点染完
        ++schemes;
        if (schemes <= 3) {
            cout << "方案 " << schemes << "：";
            for (int i = 1; i <= n; ++i) cout << color[i] << ' ';
            cout << "\n";
        }
        return;
    }
    for (int c = 1; c <= m; ++c) {                  // 每层 m 种选择
        if (!ok(t, c)) continue;                    /* 约束函数剪枝 */
        color[t] = c;                               /* ① 做选择 */
        dfs(t + 1);                                 /* ② 递归 */
        color[t] = 0;                               /* ③ 撤销选择 */
    }
}

int main() {
    /* 造一个 5 个顶点的图：0-1-2 三角形 + 2-3-4-2 三角形，共享顶点 2 */
    g[1][2] = g[2][1] = 1;
    g[2][3] = g[3][2] = 1;
    g[1][3] = g[3][1] = 1;
    g[3][4] = g[4][3] = 1;
    g[4][5] = g[5][4] = 1;
    g[3][5] = g[5][3] = 1;

    color.assign(n + 1, 0);
    dfs(1);
    cout << "用 " << m << " 种颜色共有 " << schemes << " 种染色方案（顶点编号固定，不除以置换）\n";
    cout << "搜索结点数 = " << nodes << "\n";
    return 0;
}

13.2.8 经典案例⑤：全排列与组合的生成

这是回溯法最基础、也是考得最细的一个应用。排列树与子集树的区别在这里体现得最清楚： 求全排列走排列树（n! 个叶子），求组合走子集树（2ⁿ 个叶子，再按大小筛掉）。

全排列有两种经典写法，都要会：

• 交换法（原地）：把第 t 位与第 t…n−1 位依次交换，递归处理第 t+1 位，返回后换回来。 代码极短，不需要 used 数组，但输出顺序不是字典序。
• 选择法（used 数组）：每一层从未使用的元素里挑一个，配 used[] 标记。 输出天然是字典序（前提是按升序尝试），也更容易扩展成「带重复元素去重」或「带约束的排列」。

下面的动画用选择法生成 {1,2,3} 的全排列，同时画出了排列树的当前路径与「已生成结果」列表：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

/* ============================================================
   全排列：三种写法（交换回溯 / 选择回溯 / STL next_permutation）
   ============================================================ */
vector<int> a = {1, 2, 3};
int n = 3;
vector<bool> used;
vector<int> cur;
long long nodesSwap = 0, nodesChoose = 0;

/* ---------- 写法 1：交换法（原地，输出非字典序） ---------- */
void permSwap(int t) {
    ++nodesSwap;
    if (t == n) {
        for (int v : a) cout << v;
        cout << ' ';
        return;
    }
    for (int i = t; i < n; ++i) {
        swap(a[t], a[i]);        /* ① 做选择：把第 i 个元素换到第 t 位 */
        permSwap(t + 1);         /* ② 递归 */
        swap(a[t], a[i]);        /* ③ 撤销选择：换回来 */
    }
}

/* ---------- 写法 2：选择法（used 数组，输出字典序） ---------- */
void permChoose(int t) {
    ++nodesChoose;
    if (t == n) {
        for (int v : cur) cout << v;
        cout << ' ';
        return;
    }
    for (int i = 0; i < n; ++i) {
        if (used[i]) continue;   /* 约束函数：已经被前面的位置用掉了 */
        used[i] = true; cur.push_back(a[i]);        /* ① 做选择 */
        permChoose(t + 1);                          /* ② 递归 */
        cur.pop_back(); used[i] = false;            /* ③ 撤销选择 */
    }
}

int main() {
    cout << "交换法：";
    permSwap(0);
    cout << "\n选择法：";
    used.assign(n, false);
    permChoose(0);
    cout << "\n";

    /* ---------- 写法 3：STL next_permutation（要求先升序排序） ---------- */
    vector<int> b = {1, 2, 3};
    sort(b.begin(), b.end());
    cout << "next_permutation：";
    do {
        for (int v : b) cout << v;
        cout << ' ';
    } while (next_permutation(b.begin(), b.end()));
    cout << "\n";

    cout << "交换法结点数 = " << nodesSwap << "，选择法结点数 = " << nodesChoose << "\n";
    return 0;
}

#include <iostream>
#include <vector>
using namespace std;

/* ============================================================
   组合的生成（回溯法，子集树 + 剪枝）
   从 1..n 中取 r 个数的所有组合
   ============================================================ */
int n = 5, r = 3;
vector<int> cur;
long long cnt = 0, nodes = 0;

void dfs(int start) {
    ++nodes;
    if ((int)cur.size() == r) {              /* 已选够 r 个 → 输出 */
        ++cnt;
        cout << "{ ";
        for (int v : cur) cout << v << ' ';
        cout << "}\n";
        return;
    }
    /* 剪枝：如果从 start 到 n 全部选上都不够 r 个，就没必要继续 */
    if ((int)cur.size() + (n - start + 1) < r) return;

    for (int i = start; i <= n; ++i) {
        cur.push_back(i);                    /* ① 做选择 */
        dfs(i + 1);                          /* ② 递归：只从 i 后面选，天然去重 */
        cur.pop_back();                      /* ③ 撤销选择 */
    }
}

int main() {
    dfs(1);
    cout << "C(" << n << "," << r << ") = " << cnt << " 种组合，搜索结点数 = " << nodes << "\n";
    /* 输出 10 种组合，正是杨辉三角第 5 行第 3 列的值 C(5,3) = 10 */
    return 0;
}

13.2.9 回溯法的复杂度与它的极限

现在回答本章导读里那个问题：为什么剪了枝，回溯法还是 O(2ⁿ) 或 O(n!)？

• 剪枝只影响「实际访问的结点数」，不改变「最坏情况的上界」。 剪枝函数是针对具体约束设计的，一旦遇到人为构造的、几乎不触发剪枝的输入（例如 N 皇后中 n 很大而约束极松的情形、 子集和中所有数都很小），解空间树的大部分结点仍然要访问。
• 很多问题本身就是 NP 完全的。子集和、0-1 背包的判定版本、图着色、TSP、SAT…… 在 P ≠ NP 的假设下，不存在多项式算法。所以「O(2ⁿ) 的回溯」已经是这类问题的正解了。
• 所以要靠「输入规模」来判断可行性。下表是竞赛中的经验阈值，看到 n 就能猜出该用什么算法：

13.3 分治法：划分、解决、合并

13.3.1 分治的三步骤

分治（divide and conquer，教材也译作「分而治之」）的思想可以用一句话概括： 把一个大问题切成若干个规模更小、结构相同的子问题，分别解决后再把结果合并起来。 它的三个标准步骤是：

1. 划分（Divide）：把规模为 n 的原问题分解为 k 个规模为 n/m 的子问题。 划分要尽量均匀，因为复杂度取决于递归深度。
2. 解决（Conquer）：递归地求解这些子问题。若子问题规模足够小（达到递归基， 例如 n = 1 或 n ≤ 16），就直接求解，不再递归。
3. 合并（Combine）：把子问题的解合并成原问题的解。这一步往往是整个算法中最难、也最影响复杂度的地方。

13.3.2 分治能用的四个条件

不是所有问题都能分治。教材上给出的四个条件，考试里经常原样考出来，请务必背熟：

13.3.3 经典案例：二分查找、归并排序、快速排序

这三个算法我们在第 10、12 讲都已经详细讲过，这里只从分治范式的角度重新审视一遍， 重点看「划分 / 解决 / 合并」三步分别对应代码里的哪几行，以及它们各自的主定理形态。

#include <iostream>
#include <vector>
using namespace std;

/* ============================================================
   二分查找（分治版）—— 注意它其实是"减治"：只递归一半
   划分：mid = (l + r) / 2
   解决：只递归左半或右半（这一步让 O(n) 变成 O(log n)）
   合并：无
   ============================================================ */
int bsearchRec(const vector<int>& a, int l, int r, int target) {
    if (l > r) return -1;                  // 递归出口：区间为空，找不到
    int mid = l + (r - l) / 2;             // 防溢出写法，等价于 (l+r)/2
    if (a[mid] == target) return mid;
    if (a[mid] > target) return bsearchRec(a, l, mid - 1, target);   // 只在左半找
    return bsearchRec(a, mid + 1, r, target);                        // 只在右半找
}

/* 迭代版（工程中更常用） */
int bsearchIter(const vector<int>& a, int target) {
    int l = 0, r = (int)a.size() - 1;
    while (l <= r) {
        int mid = l + (r - l) / 2;
        if (a[mid] == target) return mid;
        else if (a[mid] < target) l = mid + 1;
        else r = mid - 1;
    }
    return -1;
}

int main() {
    vector<int> a = {1, 3, 5, 7, 9, 11, 13, 15};
    cout << bsearchRec(a, 0, (int)a.size() - 1, 7) << "\n";   // 3
    cout << bsearchIter(a, 8) << "\n";                         // -1
    /* 比较次数 ≤ ⌊log2 n⌋ + 1，本例 n = 8，最多 4 次 */
    return 0;
}

#include <iostream>
#include <vector>
using namespace std;

/* ============================================================
   归并排序（分治标准形态）
   划分 O(1) + 解决 2T(n/2) + 合并 O(n)  →  T(n) = O(n log n)
   递归深度 log n，每层合并总代价 O(n)，相乘即得结论
   ============================================================ */
vector<int> tmp;

void mergeSort(vector<int>& a, int l, int r) {
    if (l >= r) return;                     // 递归出口：长度 ≤ 1 天然有序
    int mid = l + (r - l) / 2;              /* ① 划分 */
    mergeSort(a, l, mid);                   /* ② 解决左半 */
    mergeSort(a, mid + 1, r);               /* ② 解决右半 */

    /* ③ 合并：两路归并，O(n) */
    int i = l, j = mid + 1, k = l;
    while (i <= mid && j <= r) tmp[k++] = (a[i] <= a[j]) ? a[i++] : a[j++];
    while (i <= mid) tmp[k++] = a[i++];
    while (j <= r) tmp[k++] = a[j++];
    for (int t = l; t <= r; ++t) a[t] = tmp[t];
}

int main() {
    vector<int> a = {38, 27, 43, 3, 9, 82, 10};
    tmp.resize(a.size());
    mergeSort(a, 0, (int)a.size() - 1);
    for (int v : a) cout << v << ' ';
    cout << "\n";        // 3 9 10 27 38 43 82
    return 0;
}

13.3.4 最大子段和：分治 O(n log n) 与 DP O(n) 的正面对决

问题：给定长度为 n 的整数序列（可能含负数），求形如 ∑(k=i..j) a[k] 的最大值（子段必须连续）。

分治思路：把序列从中点 mid 切开，最大子段只有三种可能：

1. 完全落在左半边 [l, mid] → 递归求解；
2. 完全落在右半边 [mid+1, r] → 递归求解；
3. 跨越中点：必然包含 a[mid] 与 a[mid+1]。 于是分别向左、向右求「以 mid 结尾的最大后缀和」与「以 mid+1 开头的最大前缀和」，两者相加即可，O(n)。

第三种情况就是合并步骤，也是分治解法的精髓。递推式 T(n) = 2T(n/2) + O(n)，由主定理得 O(n log n)。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

/* ============================================================
   最大子段和：分治 O(n log n)  vs  动态规划（Kadane）O(n)
   ============================================================ */
const int NEG = -1000000000;

/* ---------- 分治版 ---------- */
int solveDC(const vector<int>& a, int l, int r) {
    if (l == r) return a[l];                       // 递归出口：单个元素
    int mid = l + (r - l) / 2;
    int bestL = solveDC(a, l, mid);                // 情况 1：完全在左半
    int bestR = solveDC(a, mid + 1, r);            // 情况 2：完全在右半

    /* 情况 3：跨越中点。左半必须含 a[mid]，右半必须含 a[mid+1] */
    int s1 = NEG, sum = 0;
    for (int i = mid; i >= l; --i) { sum += a[i]; s1 = max(s1, sum); }          // 最大后缀和
    int s2 = NEG; sum = 0;
    for (int j = mid + 1; j <= r; ++j) { sum += a[j]; s2 = max(s2, sum); }     // 最大前缀和

    return max(max(bestL, bestR), s1 + s2);
}

/* ---------- 动态规划版（Kadane 算法） ---------- */
int solveDP(const vector<int>& a) {
    int best = a[0], cur = a[0];
    for (size_t i = 1; i < a.size(); ++i) {
        cur = max(a[i], cur + a[i]);    // 要么接上前面的子段，要么从自己重新开始
        best = max(best, cur);
    }
    return best;
}

int main() {
    vector<int> a = {-2, 11, -4, 13, -5, 8, -3, 6};
    cout << "分治 = " << solveDC(a, 0, (int)a.size() - 1) << "\n";   // 26
    cout << "DP   = " << solveDP(a) << "\n";                        // 26
    /* 手推 DP：cur 依次为 -2, 11, 7, 20, 15, 23, 20, 26；best 依次为 -2, 11, 11, 20, 20, 23, 23, 26
       最大子段是 a[1..7] = 11-4+13-5+8-3+6 = 26
       分治：T(n) = 2T(n/2) + O(n) = O(n log n)
       DP  ：T(n) = O(n)，空间 O(1) —— 完胜 */
    return 0;
}

13.3.5 棋盘覆盖与循环赛日程表

这两个问题是分治在「构造性 / 安排类」问题上的经典应用，也是考研大题常客。

棋盘覆盖：一个 2^k × 2^k 的棋盘中有一个特殊方格，要求用 L 型骨牌（覆盖 3 个方格） 铺满其余所有方格。分治思路：把棋盘沿中线切成四个 2^(k−1) × 2^(k−1) 子棋盘， 特殊方格必在其中一个里；对另外三个子棋盘，在它们交界处的中心放一块 L 型骨牌， 人为地给每个子棋盘都制造出一个「特殊方格」，于是四个子问题同型，可以递归。

#include <iostream>
#include <vector>
using namespace std;

/* ============================================================
   棋盘覆盖（分治法）
   2^k × 2^k 的棋盘上有一个特殊方格，用 L 型骨牌铺满其余方格
   T(k) = 4T(k-1) + O(1)  →  O(4^k) = O(n^2)
   ============================================================ */
const int MAXN = 1 << 6;              // 最大 64 × 64
int board[MAXN][MAXN];
int tile = 0;                          // 骨牌编号，从 1 开始

/* (tr, tc) 子棋盘左上角；(dr, dc) 特殊方格；size 子棋盘边长 */
void cover(int tr, int tc, int dr, int dc, int size) {
    if (size == 1) return;                        // 递归出口：1×1 已是特殊格
    int t = ++tile;                               // 本层使用的 L 骨牌编号
    int s = size / 2;                             /* ① 划分：切成四块 */

    /* 左上角子棋盘 */
    if (dr < tr + s && dc < tc + s)               // 特殊格在其中 → 直接递归
        cover(tr, tc, dr, dc, s);
    else {                                        // 否则在它的右下角放一块骨牌，造出"特殊格"
        board[tr + s - 1][tc + s - 1] = t;
        cover(tr, tc, tr + s - 1, tc + s - 1, s);
    }
    /* 右上角子棋盘 */
    if (dr < tr + s && dc >= tc + s)
        cover(tr, tc + s, dr, dc, s);
    else {
        board[tr + s - 1][tc + s] = t;
        cover(tr, tc + s, tr + s - 1, tc + s, s);
    }
    /* 左下角子棋盘 */
    if (dr >= tr + s && dc < tc + s)
        cover(tr + s, tc, dr, dc, s);
    else {
        board[tr + s][tc + s - 1] = t;
        cover(tr + s, tc, tr + s, tc + s - 1, s);
    }
    /* 右下角子棋盘 */
    if (dr >= tr + s && dc >= tc + s)
        cover(tr + s, tc + s, dr, dc, s);
    else {
        board[tr + s][tc + s] = t;
        cover(tr + s, tc + s, tr + s, tc + s, s);
    }
}

int main() {
    int k = 2, n = 1 << k;                        // 4 × 4 棋盘
    int dr = 1, dc = 1;                           // 特殊方格在 (1,1)
    board[dr][dc] = 0;                            // 0 表示特殊方格
    cover(0, 0, dr, dc, n);

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) cout << board[i][j] << ' ';
        cout << "\n";
    }
    /* 输出（0 为特殊格）：
       1 1 3 3
       1 0 2 3
       4 2 2 5
       4 4 5 5   —— 共 5 块 L 骨牌，编号 1..5，正好铺满 15 个非特殊格 */
    return 0;
}

循环赛日程表：n = 2^k 个选手进行单循环赛（每两人赛一场），要求 n−1 天内安排完， 每人每天恰好赛一场。分治思路与棋盘覆盖异曲同工：把 n 个选手分成两组， 先递归排出组内赛程，再把左上角的表复制到右下角、左下角复制到右上角， 两组之间就自动完成了交叉比赛。

#include <iostream>
using namespace std;

/* ============================================================
   循环赛日程表（分治法）
   n = 2^k 个选手，n-1 天完成单循环，每人每天一场
   递推式：T(n) = 2T(n/2) + O(n^2/2)  →  O(n^2 · log n) 的复制量
   （每层复制总量为 O(n^2)，共 log n 层）
   ============================================================ */
const int MAXN = 1 << 4;
int a[MAXN][MAXN];                     // a[i][j] = 第 i 个选手在第 j 天的对手

/* 从左上角 (x, y) 出发，填充边长 n 的赛程块 */
void fill(int x, int y, int n) {
    if (n == 1) return;                /* 递归出口 */
    int half = n / 2;
    fill(x, y, half);                  /* 左上：a 组内部赛程 */
    fill(x + half, y, half);           /* 左下：b 组内部赛程（与左上相同） */

    /* 右上 = 左下（b 组的内部赛程对 a 组来说就是"与 b 组比赛"） */
    for (int i = 0; i < half; ++i)
        for (int j = 0; j < half; ++j)
            a[x + i][y + half + j] = a[x + half + i][y + j];

    /* 右下 = 左上 */
    for (int i = 0; i < half; ++i)
        for (int j = 0; j < half; ++j)
            a[x + half + i][y + half + j] = a[x + i][y + j];
}

int main() {
    int k = 3, n = 1 << k;             // 8 个选手，7 天
    for (int i = 0; i < n; ++i) a[i][0] = i + 1;   // 第 0 天先填自己（占位）
    fill(0, 0, n);

    cout << "选手\\天 ";
    for (int j = 1; j < n; ++j) cout << " 第" << j << "天";
    cout << "\n";
    for (int i = 0; i < n; ++i) {
        cout << "  " << i + 1 << "    ";
        for (int j = 1; j < n; ++j) cout << "   " << a[i][j] << "  ";
        cout << "\n";
    }
    return 0;
}

13.3.6 最近点对：分治的 O(n log n) 经典

在平面上给定 n 个点，求距离最近的一对点。暴力两两比较是 O(n²)； 分治可以做到 O(n log n)，是「合并步骤设计得巧妙」的最佳教材案例。

算法步骤：

1. 把所有点按 x 坐标排序（预处理一次，O(n log n)）。
2. 用一条竖线 x = mid 把点集分成左右两半（划分）。
3. 递归求左半最近距离 d1、右半最近距离 d2，令 d = min(d1, d2)（解决）。
4. 合并（关键）：最近点对可能跨越中线。只考虑距中线水平距离 < d 的点， 把它们按 y 排序，然后对每个点只检查紧随其后的 7 个点。 为什么是 7 个？因为在一个 d × 2d 的矩形内，最多只能放 8 个互不相邻（距离 ≥ d）的点， 所以每个点最多与 7 个候选比较——这一步是 O(n) 的。

于是递推式是标准的 T(n) = 2T(n/2) + O(n)，主定理第二种情形给出 O(n log n)。

#include <bits/stdc++.h>
using namespace std;

/* ============================================================
   最近点对（分治法，O(n log n)）
   关键：合并时只检查中线两侧宽度 d 的带状区域，
        且每个点最多与按 y 排序后的后 7 个点比较 → 合并为 O(n)

   竞赛写法：点的集合就是全局数组 p[] + 个数 n，
   dist / solve 都是作用在全局量上的自由函数，
   struct Point 只描述"一个点长什么样"，属于结点型，保留。
   ============================================================ */

struct Point { double x, y; };

const int MAXN = 100005;        /* 点数上限：数组开够（竞赛里按题目上限开） */
Point p[MAXN];
int n;

double dist(const Point& a, const Point& b) {
    double dx = a.x - b.x, dy = a.y - b.y;
    return sqrt(dx * dx + dy * dy);
}

/* p 已按 x 排序，返回 [l, r] 区间内的最小距离 */
double solve(int l, int r) {
    if (r - l + 1 <= 3) {                       // 小规模直接暴力，避免递归开销
        double best = 1e100;
        for (int i = l; i <= r; ++i)
            for (int j = i + 1; j <= r; ++j)
                best = min(best, dist(p[i], p[j]));
        return best;
    }
    int mid = (l + r) / 2;
    double midx = p[mid].x;                     /* ① 划分线 */
    double d = min(solve(l, mid), solve(mid + 1, r));   /* ② 分别求解 */

    /* ③ 合并：取出带状区域内的点，按 y 排序 */
    vector<Point> strip;
    for (int i = l; i <= r; ++i)
        if (fabs(p[i].x - midx) < d) strip.push_back(p[i]);
    sort(strip.begin(), strip.end(), [](const Point& a, const Point& b) { return a.y < b.y; });

    for (size_t i = 0; i < strip.size(); ++i)
        for (size_t j = i + 1; j < strip.size() && j <= i + 7; ++j) {   // 只比后 7 个
            if (strip[j].y - strip[i].y >= d) break;                   // y 差已超过 d，后面更远
            d = min(d, dist(strip[i], strip[j]));
        }
    return d;
}

int main() {
    Point a[6] = {{2, 3}, {12, 30}, {40, 50}, {5, 1}, {12, 10}, {3, 4}};
    n = 6;
    for (int i = 0; i < n; ++i) p[i] = a[i];
    sort(p, p + n, [](const Point& a, const Point& b) { return a.x < b.x; });
    printf("%.4f\n", solve(0, n - 1));   // 1.4142（点 (2,3) 与 (3,4)）
    return 0;
}

13.3.7 主定理（Master Theorem）

分治算法的复杂度几乎总是形如 T(n) = a·T(n/b) + f(n)，其中 a ≥ 1 是子问题个数，b > 1 是规模缩小倍数，f(n) 是划分与合并的代价。 主定理直接给出三种情形：

用三个经典算法各验证一遍：

#include <iostream>
#include <cmath>
using namespace std;

/* ============================================================
   主定理计算器：输入 a, b 与 f(n) 的幂次 p，判断属于哪种情形
   适用形式：T(n) = a·T(n/b) + Θ(n^p)
   ============================================================ */
void master(double a, double b, double p, const char* name) {
    double c = log(a) / log(b);            // c = log_b(a)
    cout << name << "：T(n) = " << a << "T(n/" << b << ") + Θ(n^" << p << ")\n";
    cout << "   log_b(a) = " << c << "　";
    if (p < c - 1e-9)       cout << "情形 1 → Θ(n^" << c << ")\n";
    else if (p > c + 1e-9)  cout << "情形 3 → Θ(n^" << p << ")\n";
    else                    cout << "情形 2 → Θ(n^" << c << " · log n)\n";
}

int main() {
    master(2, 2, 1, "归并排序      ");
    master(1, 2, 0, "二分查找      ");
    master(7, 2, 2, "Strassen 乘法 ");
    master(2, 2, 2, "某 O(n^2) 合并");
    master(4, 2, 1, "错误的二分递归");
    master(3, 2, 1, "Karatsuba 乘法");
    /* Karatsuba：T(n) = 3T(n/2) + O(n)，log_2(3) ≈ 1.585 > 1 → 情形 1 → O(n^1.585) */
    return 0;
}

13.3.8 分治与减治的区别

教材里还有一个容易被忽略的区分：减治（decrease and conquer）。 它与分治只差一个字，但复杂度常常差一个数量级。

13.4 贪心法：每一步都拍板，永不反悔

13.4.1 贪心的两个性质

贪心法（greedy algorithm）的做法简单到有点可疑：把问题分成若干步， 每一步都在当前可选的选择里挑一个「看起来最好」的，选定之后再也不改。 它不需要回溯、不需要记忆化、不需要填表，通常一趟排序加一次扫描就完事，复杂度往往是 O(n log n)。

但正因为「不回头」，贪心只在满足下面两个性质时才是正确的。这两个名字必须背下来：

贪心选择性质 Greedy-Choice Property

所求问题的整体最优解可以由一系列局部最优的选择达到。 也就是说：存在一个最优解，它的第一步就是我们贪心选的那个； 并且做完这一步之后，剩下的问题仍然是原问题的一个同型子问题。
这一条是贪心的合法性基础，也是证明中最难的部分——通常用交换论证（exchange argument）： 假设存在一个最优解，如果它没有做我们的贪心选择，就把它「换」成贪心选择，证明解不会变差，从而存在一个包含贪心选择的最优解。

最优子结构 Optimal Substructure

问题的最优解包含其子问题的最优解。 换句话说：如果全局最优解里用到了某个子问题的解，那个子问题的解一定也是它自己的最优解。
这一条贪心和动态规划共享——两个范式都要求最优子结构，区别只在于 DP 会保留多个候选状态， 而贪心只保留一个。
反例：最长路径问题（求两点间最长简单路径）不具备最优子结构——最长路径的子路径不一定是最长路径， 所以既不能贪心也不能 DP；而最短路径具有最优子结构，可以 Dijkstra/DP。

13.4.2 为什么贪心必须证明

这是初学者最容易犯的错误：看到「每一步都选最好的」觉得很合理，就直接写了。 问题在于，局部最优和全局最优之间没有任何天然联系。举几个真实的翻车例子：

13.4.3 反例：0-1 背包用单位价值贪心会错

我们给出一组具体数据，请务必自己算一遍：

贪心结果：只拿 A，总价值 60，总重 10， 还剩 5 的容量一点用没有（B、C 都放不下）。

真正的最优解：拿 B + C，总重 20 + 30 = 50 ≤ 50，总价值 100 + 120 = 220。

贪心错在哪？错在「单位价值最高」这个局部指标没有考虑它挤占了多少容量。 A 虽然性价比最高，但它占掉了 10 的容量，而正是这 10 的容量让 B 放不进去。 换成分数背包（物品可以切开），贪心就完全正确了——因为 A 剩下的 5 容量可以装 1/4 个 B， 拿到 60 + 25 = 85，而 B+C 全装也才 100 + 120×(20/30) = 180……等等， 分数背包下 B+C 也不是「全装」，我们重新看：容量 50，按单位价值排序 A(6.0) → B(5.0) → C(4.0)， 先装 A（用 10，得 60），再装 B（用 20，得 100），剩 20 装 C 的 20/30，得 80， 总计 60 + 100 + 80 = 240。这确实是分数背包的最优解——因为可以切开，贪心不会浪费容量。 这就是「可分割」与「不可分割」的分水岭。

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

/* ============================================================
   反例演示：0-1 背包用"单位价值贪心"会得到错误答案
   分数背包用同一个贪心策略却是正确的
   ============================================================ */
struct Item { int w, v; double ratio; };

int main() {
    vector<Item> a = {{10, 60, 0}, {20, 100, 0}, {30, 120, 0}};
    int V = 50;
    for (auto& x : a) x.ratio = (double)x.v / x.w;
    sort(a.begin(), a.end(), [](const Item& p, const Item& q) { return p.ratio > q.ratio; });

    /* --- 0-1 背包：贪心（错误示范） --- */
    int w1 = 0, v1 = 0;
    for (auto& x : a)
        if (w1 + x.w <= V) { w1 += x.w; v1 += x.v; }
    cout << "0-1 背包贪心结果：重量 " << w1 << "，价值 " << v1 << "（错误！）\n";

    /* --- 0-1 背包：暴力枚举求真正最优（n 很小） --- */
    int n = a.size(), best = 0;
    for (int mask = 0; mask < (1 << n); ++mask) {
        int w = 0, v = 0;
        for (int i = 0; i < n; ++i) if (mask >> i & 1) { w += a[i].w; v += a[i].v; }
        if (w <= V) best = max(best, v);
    }
    cout << "0-1 背包真正最优：价值 " << best << "\n";

    /* --- 分数背包：同一个贪心策略（正确） --- */
    double w2 = 0, v2 = 0;
    for (auto& x : a) {
        if (w2 + x.w <= V) { w2 += x.w; v2 += x.v; }
        else { v2 += x.ratio * (V - w2); w2 = V; break; }   // 装一部分
    }
    cout << "分数背包贪心结果：重量 " << w2 << "，价值 " << v2 << "（正确）\n";
    /* 输出：
       0-1 背包贪心结果：重量 10，价值 60（错误！）
       0-1 背包真正最优：价值 220
       分数背包贪心结果：重量 50，价值 240（正确） */
    return 0;
}

13.4.4 经典案例：活动安排（区间调度）

问题：有 n 个活动，第 i 个活动占用时间区间 [s_i, f_i)。 同一时刻只能进行一个活动，求最多能安排多少个活动（区间互不重叠）。

贪心策略：按结束时间 f_i 从小到大排序，依次选取「开始时间 ≥ 上一个被选活动的结束时间」的活动。

为什么是结束时间而不是开始时间或持续时间？三个理由：

• 按开始时间最早：反例 [0,100) 与 [1,2), [3,4), [5,6)—— 贪心选第一个就只得到 1 个活动，最优是 3 个。
• 按持续时间最短：反例 [0,5)、[5,10)、[4,6)—— 最短的是 [4,6)，选了它之后 [0,5) 与 [5,10) 都放不下了（一个重叠左端、一个重叠右端）， 只得到 1 个，最优是 2 个。
• 按结束时间最早：直觉上「越早结束，留给后面的时间就越多」。 严格证明用交换论证：设最优解的第一个活动是 a，贪心选的是 g， 因为 f_g ≤ f_a，把 a 换成 g 后，剩下的可选空间只会更大不会更小， 所以替换后仍是最优解。

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

/* ============================================================
   活动安排 / 区间调度（贪心法）
   贪心策略：按结束时间升序排序，依次选取与已选区间不重叠的
   正确性依据：贪心选择性质（交换论证）+ 最优子结构
   复杂度：排序 O(n log n) + 扫描 O(n)
   ============================================================ */
struct Act { int s, f, id; };

int main() {
    vector<Act> a = {
        {1, 3, 1}, {1, 7, 2}, {1, 2, 3}, {3, 6, 4}, {4, 6, 5}, {7, 9, 6}
    };
    /* ① 按结束时间升序 */
    sort(a.begin(), a.end(), [](const Act& p, const Act& q) { return p.f < q.f; });

    /* ② 一趟扫描，能选就选 */
    vector<int> chosen;
    int lastEnd = -1000000000;
    for (const auto& x : a) {
        if (x.s >= lastEnd) {          // 开始时间不早于上一个的结束时间 → 不重叠
            chosen.push_back(x.id);
            lastEnd = x.f;
        }
    }

    cout << "最多安排 " << chosen.size() << " 个活动：";
    for (int id : chosen) cout << id << ' ';
    cout << "\n";        // 最多安排 3 个活动：3 4 6
    return 0;
}

13.4.5 经典案例：分数背包与找零钱

分数背包（fractional knapsack）：物品可以任意切割，求装进容量 V 的背包能得到的最大价值。 贪心策略：按单位价值 v_i / w_i 降序，能整件装就整件装，装不下就把最后一件切一部分塞满。 复杂度 O(n log n)（瓶颈在排序）。

为什么它正确？因为如果最优解里存在「装了单位价值较低的物品 X，却没装满单位价值更高的物品 Y」， 那么把 X 的一点点换成 Y 的一点点，总重量不变而总价值上升，矛盾。所以最优解必然优先装高单位价值的物品—— 这正是贪心选择性质的交换论证。

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

/* ============================================================
   分数背包（贪心法，物品可切割）—— 与 13.5.3 的 0-1 背包对照
   贪心策略：按单位价值降序，依次装满；最后一件切一部分
   ============================================================ */
struct Item { int w, v; double r; };

int main() {
    vector<Item> a = {{10, 60, 0}, {20, 100, 0}, {30, 120, 0}};
    int V = 50;
    for (auto& x : a) x.r = (double)x.v / x.w;
    sort(a.begin(), a.end(), [](const Item& p, const Item& q) { return p.r > q.r; });

    double totalV = 0, totalW = 0;
    for (const auto& x : a) {
        if (totalW + x.w <= V) {                 // 整件装下
            totalW += x.w; totalV += x.v;
            cout << "装入完整物品 (w=" << x.w << ", v=" << x.v << ")\n";
        } else {                                  // 切开装一部分
            double take = V - totalW;
            totalV += x.r * take;
            totalW = V;
            cout << "装入 " << take << "/" << x.w << " 个 (w=" << x.w << ", v=" << x.v << ")\n";
            break;                                // 背包已满
        }
    }
    printf("总重量 %.1f，总价值 %.1f\n", totalW, totalV);
    /* 输出：装入完整物品 (w=10, v=60) / (w=20, v=100) / 装入 20/30 个 (w=30, v=120)
             总重量 50.0，总价值 240.0  —— 对比 0-1 背包的 220 */
    return 0;
}

找零钱问题（coin change）：用最少的硬币凑出金额 k，硬币面值给定且每种无限多。 贪心策略是「每次用不超过余额的最大面值」。它对人民币面值（1、5、10、20、50、100……）是正确的， 但对任意面值组合会失效。

注意第三行与第四行的对比：同一组面值，目标 6 时贪心错、目标 8 时贪心对。 这就是贪心最危险的地方——它可能在某些数据上碰巧正确，让你误以为整个算法是对的。 找零钱的最优解必须用完全背包（见 13.5.3 的 ②），时间复杂度 O(k·m)。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int INF = 1000000000;

/* 贪心法：每次取不超过余额的最大面值。对任意面值集合不一定正确 */
int greedy(const vector<int>& coin, int k) {
    vector<int> c = coin;
    sort(c.rbegin(), c.rend());
    int cnt = 0;
    for (int v : c) { cnt += k / v; k %= v; }
    return k == 0 ? cnt : -1;          // 剩余不为 0 表示凑不出来
}

/* 完全背包（动态规划）：求最少硬币数，一定正确 */
int dpMin(const vector<int>& coin, int k) {
    vector<int> dp(k + 1, INF);
    dp[0] = 0;
    for (int v : coin)                               // 每种硬币
        for (int j = v; j <= k; ++j)                 // 正序：完全背包
            dp[j] = max(dp[j], dp[j - v] + w);
    return dp[k] >= INF ? -1 : dp[k];
}

int main() {
    vector<int> c1 = {1, 5, 10, 20, 50, 100};
    cout << "人民币面值 86：" << greedy(c1, 86) << " vs " << dpMin(c1, 86) << "\n";   // 5 vs 5
    vector<int> c2 = {1, 3, 4};
    cout << "面值{1,3,4} 找 6：" << greedy(c2, 6) << " vs " << dpMin(c2, 6) << "\n";  // 3 vs 2（贪心错）
    vector<int> c3 = {1, 6, 10};
    cout << "面值{1,6,10} 找 18：" << greedy(c3, 18) << " vs " << dpMin(c3, 18) << "\n"; // 4 vs 3（贪心错）
    return 0;
}

13.4.6 经典案例：区间覆盖

问题：给定一条线段 [1, T] 和 n 个可选区间 [l_i, r_i]， 用最少的区间把 [1, T] 完全覆盖住。

贪心策略：维护一个「当前已经覆盖到 cur」的指针，初始 cur = 1。 每次在所有满足 l_i ≤ cur 的区间里，选 r_i 最大的那个， 把 cur 更新为 r_i，区间计数 +1。重复直到 cur ≥ T。

这与活动安排是「对偶」的两类区间贪心，请对照记忆：

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

/* ============================================================
   区间覆盖（贪心法）：用最少的区间覆盖 [1, T]
   贪心：在"左端点 ≤ 当前已覆盖位置"的区间里，选右端点最远的那个
   复杂度：排序 O(n log n) + 扫描 O(n)
   ============================================================ */
struct Seg { int l, r; };

int main() {
    vector<Seg> s = {{1, 4}, {2, 6}, {3, 5}, {5, 9}, {7, 10}, {9, 12}};
    int T = 12;
    sort(s.begin(), s.end(), [](const Seg& a, const Seg& b) { return a.l < b.l; });

    int cur = 1, cnt = 0;
    size_t i = 0;
    while (cur < T) {
        int far = cur;                        // 本␣轮能推到的最远位置
        bool moved = false;
        while (i < s.size() && s[i].l <= cur) {          // 所有"接得上"的区间
            if (s[i].r > far) { far = s[i].r; moved = true; }
            ++i;
        }
        if (!moved) { cout << "无法覆盖到 " << T << "\n"; return 0; }
        ++cnt;
        cout << "第 " << cnt << " 段覆盖到 " << far << "\n";
        cur = far;
    }
    cout << "最少需要 " << cnt << " 个区间\n";
    /* 第 1 段覆盖到 4 ／ 第 2 段覆盖到 9 ／ 第 3 段覆盖到 12 ／ 最少需要 3 个区间 */
    return 0;
}

13.4.7 贪心与 DP 的关系：只保留一个状态的 DP

这是本章最重要的一句话之一：贪心就是「每一步只保留一个状态的动态规划」。 我们用一个统一视角把两者串起来。

反过来看：如果你写出一个 DP，发现对于每个状态，转移方程里只有一项可能是最优 （另外那些候选永远不可能赢），那么这个 DP 就可以直接砍成贪心。 例如活动安排：设 dp[i] 为「前 i 个活动中能选的最大数量」， 转移是 dp[i] = max(dp[i−1], dp[p(i)] + 1)（p(i) 是 i 之前最后一个不重叠的活动）， 按结束时间排序后，dp[p(i)] + 1 总是 ≥ dp[i−1]， 于是 max 退化成「直接选」，DP 就简化成了贪心。

13.4.8 已在前面章节讲过的两个贪心经典

13.5 动态规划（本章核心）

欢迎来到本章篇幅最大、也最关键的一节。前面四节我们一直在铺垫： 回溯法教会我们「把求解过程看成一棵决策树」，分治教会我们「把问题拆小」， 贪心教会我们「只保留一个状态」。动态规划正是这三条线的交汇点—— 它把回溯的解空间树按「状态」重新组织，把分治的递归结构配上记忆化， 再用「只保留有价值的状态」来压缩空间。

但在正式开始之前，先破除一个流行的误解：动态规划（Dynamic Programming）这个名字里的 "Programming" 不是「编程」，而是「表格法 / 规划」的意思（来自运筹学里的 mathematical programming， 指用表格安排计划）。它和「写代码」没有半点关系。所以 DP 的核心动作始终是填表， 这也是本章有那么多表格动画的原因。

13.5.1 从记忆化搜索到递推：重叠子问题是万恶之源

我们从一个最熟悉的例子开始：斐波那契数列。

直接照着定义写递归：

#include <iostream>
using namespace std;

/* 朴素递归求斐波那契：教学上漂亮，实际上慢得可怕 */
long long calls = 0;                 // 统计递归调用次数

long long fib(int n) {
    ++calls;
    if (n <= 2) return 1;
    return fib(n - 1) + fib(n - 2);
}

int main() {
    for (int n = 10; n <= 40; n += 10) {
        calls = 0;
        long long r = fib(n);
        cout << "fib(" << n << ") = " << r << "　递归调用次数 = " << calls << "\n";
    }
    /* fib(40) 的调用次数约为 3.3 亿次，普通电脑要跑好几秒；
       而 fib(50) 就要跑几分钟——明明答案只有 50 个数，却算了 2^n 次 */
    return 0;
}

为什么会这样？把 fib(5) 的递归树画出来就明白了：

记忆化搜索（memoization / memoized search）就是在递归的基础上加一个「备忘录」数组： 进入函数先查表，表里有值就直接返回；算完了先把结果写进表，再返回。 就这么一个小改动，复杂度从 O(2ⁿ) 掉到 O(n)。

#include <iostream>
#include <vector>
using namespace std;

/* ============================================================
   记忆化搜索 vs 自底向上递推 —— 同一个问题的两种 DP 写法
   ============================================================ */
vector<long long> memo;
long long callsMemo = 0;

/* ---------- 写法 1：记忆化搜索（自顶向下） ---------- */
long long fibMemo(int n) {
    ++callsMemo;
    if (n <= 2) return 1;
    if (memo[n] != -1) return memo[n];      // ① 查表：算过就直接返回
    return memo[n] = fibMemo(n - 1) + fibMemo(n - 2);   // ② 存表
}

/* ---------- 写法 2：递推（自底向上） ---------- */
long long fibIter(int n) {
    if (n <= 2) return 1;
    long long a = 1, b = 1, c = 0;
    for (int i = 3; i <= n; ++i) { c = a + b; a = b; b = c; }   // 滚动变量，空间 O(1)
    return c;
}

int main() {
    int n = 90;
    memo.assign(n + 1, -1);
    cout << "记忆化 fib(" << n << ") = " << fibMemo(n) << "，函数调用次数 = " << callsMemo << "\n";
    cout << "递推   fib(" << n << ") = " << fibIter(n) << "\n";
    /* 记忆化：调用次数约 2n 次（每个状态最多算一次，但函数入口会被访问两次）
       递推  ：循环 n-2 次，无递归开销
       朴素递归：fib(90) 需要 10^18 量级的调用，永远算不完 */
    return 0;
}

再看一个更能说明问题的例子：数字三角形。它同时展示了「重叠子问题」和「最优子结构」。

问题：给定一个 n 层的数字三角形，从顶部出发，每步可以走到下一层的正下方或右下方， 求一条到底部的路径，使路径上数字之和最大。

朴素搜索：每层 2 个选择，共 2^(n−1) 条路径，n = 30 时就是 5 亿条。 但不同的路径会在同一格相遇！例如第 3 行第 2 列的数字，既可以从「下、右」到达，也可以从「右、下」到达。 到达这一格之后，往后能取得的最大值只与这一格的位置有关，与前面怎么走的无关—— 这就是无后效性（no aftereffect），也说明这个问题的状态就是「格子坐标」。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

/* ============================================================
   数字三角形（线性 DP 入门）
   状态：dp[i][j] = 从底部走到第 i 行第 j 列能获得的最大和
   转移：dp[i][j] = a[i][j] + max(dp[i+1][j], dp[i+1][j+1])
   边界：dp[n][j] = a[n][j]
   遍历顺序：i 从 n-1 递减到 1（因为 dp[i] 依赖 dp[i+1]）
   ============================================================ */
int main() {
    int n = 5;
    vector<vector<int>> a(n + 1, vector<int>(n + 2, 0));
    a[1][1] = 7;
    a[2][1] = 3;  a[2][2] = 8;
    a[3][1] = 8;  a[3][2] = 1;  a[3][3] = 0;
    a[4][1] = 2;  a[4][2] = 7;  a[4][3] = 4;  a[4][4] = 4;
    a[5][1] = 4;  a[5][2] = 5;  a[5][3] = 2;  a[5][4] = 6;  a[5][5] = 5;

    /* ---------- 写法 1：二维 DP ---------- */
    vector<vector<int>> dp(n + 1, vector<int>(n + 2, 0));
    for (int j = 1; j <= n; ++j) dp[n][j] = a[n][j];          // 初始化：底层
    for (int i = n - 1; i >= 1; --i)                          // 自底向上
        for (int j = 1; j <= i; ++j)
            dp[i][j] = a[i][j] + max(dp[i + 1][j], dp[i + 1][j + 1]);
    cout << "二维 DP 最大值 = " << dp[1][1] << "\n";            // 30

    /* ---------- 写法 2：滚动数组（一维） ---------- */
    vector<int> f(n + 2, 0);
    for (int j = 1; j <= n; ++j) f[j] = a[n][j];
    for (int i = n - 1; i >= 1; --i)
        for (int j = 1; j <= i; ++j)
            f[j] = a[i][j] + max(f[j], f[j + 1]);             // 用本层的旧值，天然无冲突
    cout << "滚动数组最大值 = " << f[1] << "\n";               // 30

    /* 路径：7 → 3 → 8 → 7 → 5，和为 30 */
    return 0;
}

下面这张表手工推一遍就能彻底理解「为什么自底向上可以滚成一行」：

13.5.2 DP 的三要素、四步法与解题流程

很多人学 DP 的痛苦在于「看了题解觉得懂了，自己做就完全想不到」。 根本原因是没有一套固定的动作。下面这套流程请务必背下来，做题时一条一条对着走。

DP 的三要素

① 状态 State

用一组变量（下标、容量、集合……）完整描述「问题的一个子问题」。 好的状态必须满足无后效性：只要状态确定了，后面的决策就与「怎么到达这个状态」无关。
状态设计得好坏，直接决定 DP 能不能做、复杂度是多少。写状态时要问自己： 「如果我知道这几个量，能不能唯一确定接下来该怎么做？还需要知道别的吗？」

② 转移方程 Transition

描述「一个状态如何由更小的状态推出来」，也就是决策的数学表达。 常见形式：取 max/min（求最优值）、求和（求方案数）、取 or/and（求可行性）。
写转移时把「最后一步做了什么决策」想清楚，所有分支列全，不要漏。

③ 边界与初始化 Boundary

最小的、无法再分解的状态该取什么值。这是 DP 最容易出错的地方， 尤其是「恰好装满」与「至多装满」的初始化区别（见 13.5.3 的 ⑤）。
另外要确定遍历顺序：必须保证「算某个状态时，它依赖的状态已经算好了」。

13.5.3 线性 DP（一）：数字三角形、LIS、LCS、最大子段和

线性 DP 是最基础的一类：状态只跟「处理到第几个元素」有关，通常是一维或二维数组， 沿一个或两个方向递推。这一节把四个必考模型一次讲完。

（1）最长上升子序列 LIS

问题：给定长度为 n 的序列 a，求最长的严格上升子序列的长度（子序列不要求连续）。

O(n²) 解法：定义 dp[i] = 「以 a[i] 结尾的最长上升子序列长度」。 注意这个「以 i 结尾」的限制至关重要——它保证了无后效性（后面的元素只需要知道前面以谁结尾、长度多少）。 转移：dp[i] = 1 + max{ dp[j] : j < i 且 a[j] < a[i] }，没有这样的 j 时 dp[i] = 1。 答案是 max(dp[i])，不是 dp[n]——这是个经典易错点。

O(n log n) 解法（贪心 + 二分）：维护一个数组 tails，其中 tails[len] 表示「所有长度为 len 的上升子序列中，结尾元素的最小值」。 这个数组一定是严格单调递增的（否则可以构造出更长的子序列）。 遍历每个 a[i]：在 tails 里二分找到第一个 ≥ a[i] 的位置，把它替换成 a[i]； 如果所有元素都 < a[i]，就追加到末尾。最终 tails 的长度就是 LIS 长度。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

/* ============================================================
   LIS（最长上升子序列）—— O(n^2) DP 与 O(n log n) 贪心+二分
   ============================================================ */

/* ---------- 解法 1：O(n^2) 动态规划 ---------- */
int lisN2(const vector<int>& a) {
    int n = a.size(), best = 0;
    vector<int> dp(n, 1);                      // dp[i]：以 a[i] 结尾的 LIS 长度，最小为 1
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < i; ++j)
            if (a[j] < a[i]) dp[i] = max(dp[i], dp[j] + 1);   // 严格上升用 <，非降用 <=
        best = max(best, dp[i]);               // 答案要取全局最大值！
    }
    return best;
}

/* ---------- 解法 2：O(n log n) 贪心 + 二分 ---------- */
int lisNLogN(const vector<int>& a, vector<int>* outTails = nullptr) {
    vector<int> tails;                        // tails[len-1] = 长度 len 的上升子序列的最小结尾
    for (int x : a) {
        /* lower_bound：第一个 >= x 的位置（严格上升用 lower_bound，
           非降子序列改用 upper_bound） */
        auto it = lower_bound(tails.begin(), tails.end(), x);
        if (it == tails.end()) tails.push_back(x);   // 比所有结尾都大 → 可以接在最长的后面
        else *it = x;                                // 否则替换掉，让结尾更小（更有潜力）
    }
    if (outTails) *outTails = tails;
    return tails.size();
}

int main() {
    vector<int> a = {10, 9, 2, 5, 3, 7, 101, 18};
    cout << "O(n^2)     LIS = " << lisN2(a) << "\n";          // 4
    vector<int> tails;
    cout << "O(n log n) LIS = " << lisNLogN(a, &tails) << "\n"; // 4
    cout << "最终的 tails = ";
    for (int v : tails) cout << v << ' ';
    cout << "\n";     // 2 3 7 18
    /* 注意：tails 不是某个具体的 LIS！它只是"各长度的最小结尾"，
       例如 2 3 7 18 确实是本例的一个 LIS，但一般情况下 tails 不等于任何 LIS。
       要输出具体方案必须额外记录前驱，或用 O(n^2) 的 DP + 回溯。 */
    return 0;
}

下面的动画把 tails 数组的更新过程与二分位置逐帧画出来：

（2）最长公共子序列 LCS

问题：给定两个序列 A（长度 n）与 B（长度 m），求它们最长的公共子序列的长度与内容。 注意「子序列」不要求连续，这与第 05 讲的「子串（连续）」是两回事。

状态：dp[i][j] = 「A 的前 i 个字符与 B 的前 j 个字符的最长公共子序列长度」。

转移：考虑 A[i] 与 B[j]（1 基下标）：

边界：dp[0][j] = dp[i][0] = 0（空串与任何串的 LCS 长度为 0）。 答案是 dp[n][m]。遍历顺序：i 从 1 到 n，j 从 1 到 m（或反过来，都行，只要 i−1 / j−1 先算好）。 复杂度 O(nm)（朴素 LCS 没有已知的通用次二次算法，这是它和 LIS 的重要区别）。

下表完整填出了 A = "ABCBDAB"、B = "BDCABA" 的 dp 表，请对照动画逐格验证：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

/* ============================================================
   LCS（最长公共子序列）
   状态：dp[i][j] = A 前 i 个字符与 B 前 j 个字符的 LCS 长度
   转移：相等 → dp[i-1][j-1] + 1；不等 → max(dp[i-1][j], dp[i][j-1])
   ============================================================ */
int lcsLen(const string& A, const string& B) {
    int n = A.size(), m = B.size();
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));   // 第 0 行/列自动为 0（边界）
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j) {
            if (A[i - 1] == B[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
            else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
        }
    return dp[n][m];
}

/* 滚动数组版：只保留两行（求长度够用，但无法还原路径） */
int lcsRolling(const string& A, const string& B) {
    int n = A.size(), m = B.size();
    vector<int> prev(m + 1, 0), cur(m + 1, 0);
    for (int i = 1; i <= n; ++i) {
        fill(cur.begin(), cur.end(), 0);      // 关键：交换后 cur 里是上一轮的数据，必须先清 0
        for (int j = 1; j <= m; ++j) {
            if (A[i - 1] == B[j - 1]) cur[j] = prev[j - 1] + 1;
            else cur[j] = max(prev[j], cur[j - 1]);
        }
        swap(prev, cur);                      // 本层变成下一层的"上一层"
    }
    return prev[m];
}

/* 还原一条最长公共子序列：从 (n,m) 往回走 */
string lcsPath(const string& A, const string& B) {
    int n = A.size(), m = B.size();
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j) {
            if (A[i - 1] == B[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
            else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
        }
    string res;
    int i = n, j = m;
    while (i > 0 && j > 0) {
        if (A[i - 1] == B[j - 1]) { res.push_back(A[i - 1]); --i; --j; }   // 来自左上角
        else if (dp[i - 1][j] >= dp[i][j - 1]) --i;                        // 来自上方
        else --j;                                                          // 来自左方
    }
    reverse(res.begin(), res.end());          // 我们是倒着走的，要翻过来
    return res;
}

int main() {
    string A = "ABCBDAB", B = "BDCABA";
    cout << "LCS 长度 = " << lcsLen(A, B) << "\n";        // 4
    cout << "滚动数组 = " << lcsRolling(A, B) << "\n";    // 4
    cout << "一条 LCS = " << lcsPath(A, B) << "\n";      // BCBA（也可以是 BDAB 等）
    return 0;
}

（3）最大子段和与 Kadane 算法

我们在 13.3.4 用分治解过它，现在用 DP 重新看一遍，体会「DP 如何利用阶段结构把 O(n log n) 打成 O(n)」。

状态：f[i] = 「以 a[i] 结尾的最大子段和」。 关键在于「以 i 结尾」这个限制——它把「子段从哪开始」这个二维信息压缩成了一维， 因为一旦确定了结尾位置，前面那段要不要，只看它是不是正贡献。

直觉解释：如果 f[i−1] > 0，那么前面的积累是财富，接上； 如果 f[i−1] ≤ 0，前面的积累是包袱，直接从 a[i] 重新开始。 由于 f[i] 只依赖 f[i−1]，可以用一个变量滚动，空间 O(1)。 这个一行核心代码的算法就叫 Kadane 算法。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

/* ============================================================
   最大子段和（Kadane 算法，线性 DP）
   f[i] = 以 a[i] 结尾的最大子段和 = max(a[i], f[i-1] + a[i])
   答案 = max over i of f[i]（注意不是 f[n]！）
   空间可优化到 O(1)：只需保留 f[i-1]
   ============================================================ */
int kadane(const vector<int>& a, int& bestL, int& bestR) {
    int best = a[0], cur = a[0];
    int start = 0;                       // 当前子段的起点
    bestL = bestR = 0;
    for (int i = 1; i < (int)a.size(); ++i) {
        if (cur < 0) { cur = a[i]; start = i; }        // 前面是包袱 → 从这里重新开始
        else cur += a[i];                              // 前面是财富 → 接上
        if (cur > best) { best = cur; bestL = start; bestR = i; }
    }
    return best;
}

int main() {
    vector<int> a = {-2, 11, -4, 13, -5, 8, -3, 6};
    int l, r;
    int ans = kadane(a, l, r);
    cout << "最大子段和 = " << ans << "，区间 [" << l << ", " << r << "]\n";   // 26，区间 [1, 7]
    /* 逐项看 f：-2, 11, 7, 20, 15, 23, 20, 26
       best：    -2, 11, 11, 20, 20, 23, 23, 26
       时间 O(n)，空间 O(1) —— 与分治的 O(n log n) 对比，这是 DP 的完胜 */
    return 0;
}

13.5.4 背包问题（重点，要讲透）

背包问题是动态规划最好的练兵场：它的状态定义极简单（「前 i 件物品、容量 j」）， 但几乎每一种变体都会引入一个新的坑。这一节我们把 01 背包、完全背包、多重背包、 分组背包 / 树上背包、方案数与初始化区别全部走一遍，每一种都配手工填的 dp 表。

（1）01 背包：每件物品最多选一次

问题：有 n 件物品，第 i 件重 w[i]、价值 v[i]， 背包容量 V。每件物品只能选 0 次或 1 次，求能装的最大总价值。

状态定义：dp[i][j] = 「只考虑前 i 件物品、背包容量为 j 时能获得的最大价值」。

转移方程：面对第 i 件物品，只有两种决策：

也就是一行代码：

/* 01 背包核心转移（二维写法）：
   dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])   (j >= w[i])
   边界：dp[0][j] = 0（一件都不选，价值为 0）
   答案：dp[n][V]
   复杂度：时间 O(nV)，空间 O(nV) → 可滚成一维 O(V) */
for (int i = 1; i <= n; ++i)
    for (int j = 0; j <= V; ++j) {
        dp[i][j] = dp[i - 1][j];                       // 不选第 i 件
        if (j >= w[i]) dp[i][j] = max(dp[i][j], dp[i - 1][j - w[i]] + v[i]);   // 选
    }

注意转移里用的是 dp[i−1][...]（上一层），这一点是全部坑的根源。 下面用 4 件物品、容量 8 的手工表来完整验证：

物品：① w=2, v=3　② w=3, v=4　③ w=4, v=5　④ w=5, v=6　容量 V = 8

修正后的正确表格如下（请以此为准）：

一维滚动数组：注意到 dp[i][*] 只依赖 dp[i−1][*]， 所以我们可以只用一个一维数组 dp[j]， 在第 i 轮循环开始时它存的是 dp[i−1][*]，循环结束后变成 dp[i][*]。 转移方程简化为：

下面这个动画把 01 背包的 dp 表逐格填出来，同时实时显示「当前物品 / 当前容量 / 取的是哪个旧值 / 为什么必须倒序」：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

/* ============================================================
   01 背包：二维 DP → 一维滚动数组（容量倒序）
   物品下标 1..n；w[i] 重量，v[i] 价值；V 容量
   时间 O(nV)，空间 O(V)
   ============================================================ */
int n = 4, V = 8;
int w[5] = {0, 2, 3, 4, 5};
int v[5] = {0, 3, 4, 5, 6};

int main() {
    /* ---------- 写法 1：二维 DP（便于理解与还原方案） ---------- */
    vector<vector<int>> dp(n + 1, vector<int>(V + 1, 0));
    for (int i = 1; i <= n; ++i)
        for (int j = 0; j <= V; ++j) {
            dp[i][j] = dp[i - 1][j];                              // 不选第 i 件
            if (j >= w[i])
                dp[i][j] = max(dp[i][j], dp[i - 1][j - w[i]] + v[i]);  // 选第 i 件
        }
    cout << "二维 DP 最优价值 = " << dp[n][V] << "\n";              // 10

    /* ---------- 写法 2：一维滚动数组（容量必须倒序！） ---------- */
    vector<int> f(V + 1, 0);
    for (int i = 1; i <= n; ++i)
        for (int j = V; j >= w[i]; --j)          // ← 倒序：保证 f[j-w[i]] 是上一层（i-1）的旧值
            f[j] = max(f[j], f[j - w[i]] + v[i]);
    cout << "一维 DP 最优价值 = " << f[V] << "\n";                  // 10

    /* ---------- 回溯法还原最优方案（用二维表倒推） ---------- */
    vector<int> pick;
    int j = V;
    for (int i = n; i >= 1; --i) {
        if (j >= w[i] && dp[i][j] == dp[i - 1][j - w[i]] + v[i]) {  // 说明第 i 件被选了
            pick.push_back(i);
            j -= w[i];
        }
    }
    cout << "选取物品：";
    for (int k = (int)pick.size() - 1; k >= 0; --k) cout << pick[k] << ' ';
    cout << "\n";        // 选取物品：2 4（w = 3+5 = 8, v = 4+6 = 10）
    return 0;
}

（2）完全背包：每件物品无限件

问题：每件物品可以选任意多件（只要装得下），求最大总价值。

状态与转移：仍然是 dp[i][j] = 前 i 件、容量 j 的最大价值，但转移变了：

注意第二个分支里是 dp[i][...] 而不是 dp[i−1][...]—— 因为选了第 i 件之后，第 i 件还可以再选。这一个下标的差别，就对应了循环方向的差别：

手工填出完全背包的表（同一组物品，容量 8）：

下面的动画可以并排对比正序与倒序两种填表方式，看清 dp 数组每一轮是怎么被更新的：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

/* ============================================================
   完全背包：每件物品无限件
   一维写法与 01 背包只差一个循环方向：容量【正序】
   ============================================================ */
int n = 4, V = 8;
int w[5] = {0, 2, 3, 4, 5};
int v[5] = {0, 3, 4, 5, 6};

int main() {
    vector<int> f(V + 1, 0);
    for (int i = 1; i <= n; ++i)
        for (int j = w[i]; j <= V; ++j)         // ← 正序：用本层刚更新的新值，相当于"可以再选一件"
            f[j] = max(f[j], f[j - w[i]] + v[i]);

    cout << "完全背包最优价值 = " << f[V] << "\n";        // 12（四件 ①）
    for (int j = 0; j <= V; ++j) cout << f[j] << ' ';
    cout << "\n";     // 0 0 3 3 6 6 9 9 12

    /* 另一个等价写法：先枚举容量、再枚举物品，结果相同（完全背包可以交换两层循环） */
    vector<int> g(V + 1, 0);
    for (int j = 1; j <= V; ++j)
        for (int i = 1; i <= n; ++i)
            if (j >= w[i]) g[j] = max(g[j], g[j - w[i]] + v[i]);
    cout << "交换循环顺序后 = " << g[V] << "\n";          // 12（01 背包就不能交换！）
    return 0;
}

（3）多重背包：每件物品有 s 件

问题：第 i 件物品有 s[i] 件（有限件），求最大价值。 它是 01 背包与完全背包的中间形态：s = 1 时是 01 背包，s = ∞ 时是完全背包。

三种写法的复杂度差别很大，考试与竞赛都常考：

二进制拆分为什么正确？因为任何一个 0 到 s 之间的整数，都能用 1, 2, 4, …, 2^(k−1), s − (2^k − 1) 这些数的子集和唯一表示。 例如 s = 13：拆成 1, 2, 4, 6（因为 1+2+4 = 7，剩 13−7 = 6）， 这四捆的组合可以表示 0..13 中的任何件数（1+2+4 = 7 覆盖 0..7，加上 6 覆盖 6..13，合并覆盖 0..13）。 于是「13 件同种物品」被换成了「4 件互不相同的 01 物品」，物品数从 13 降到 4。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

/* ============================================================
   多重背包：每件物品有 s[i] 件（有限）
   ① 朴素 O(n·V·s)　② 二进制拆分 O(n·V·log s)　③ 单调队列 O(n·V)
   ============================================================ */
int n = 3, V = 12;
int w[4] = {0, 2, 3, 4};
int v[4] = {0, 3, 4, 5};
int s[4] = {0, 3, 2, 4};      // 每种物品的件数上限

/* ---------- ① 朴素写法：枚举取几件 ---------- */
int multiNaive() {
    vector<int> dp(V + 1, 0);
    for (int i = 1; i <= n; ++i)
        for (int j = V; j >= w[i]; --j)                // 倒序保证"上一层的旧值"
            for (int k = 1; k <= s[i] && k * w[i] <= j; ++k)
                dp[j] = max(dp[j], dp[j - k * w[i]] + k * v[i]);
    return dp[V];
}

/* ---------- ② 二进制拆分（推荐） ---------- */
int multiBinary() {
    vector<int> dp(V + 1, 0);
    for (int i = 1; i <= n; ++i) {
        int cnt = s[i];
        for (int k = 1; cnt > 0; k <<= 1) {            // k = 1, 2, 4, 8, ...
            int take = min(k, cnt);                    // 最后可能不足 k 件
            cnt -= take;
            int nw = take * w[i], nv = take * v[i];    // 把 take 件"捆"成一件 01 物品
            for (int j = V; j >= nw; --j)              // 01 背包：倒序
                dp[j] = max(dp[j], dp[j - nw] + nv);
        }
    }
    return dp[V];
}

/* ---------- ③ 单调队列优化 O(n·V) ---------- */
int multiDeque() {
    vector<int> dp(V + 1, 0), ndp(V + 1, 0);
    vector<int> q(V + 2);                              // 单调队列存下标
    for (int i = 1; i <= n; ++i) {
        int W = w[i], Val = v[i], S = s[i];
        for (int r = 0; r < W; ++r) {                  // 按 j mod W 分组，组内独立
            int head = 0, tail = 0;                    // [head, tail) 为队列区间
            for (int k = 0; r + k * W <= V; ++k) {
                int j = r + k * W;
                /* 把 dp[j] - k*Val 放进队列，保持单调递减 */
                int cur = dp[j] - k * Val;
                while (head < tail && dp[r + q[tail - 1] * W] - q[tail - 1] * Val <= cur) --tail;
                q[tail++] = k;
                /* 弹出窗口外的（超过 S 件） */
                while (q[head] < k - S) ++head;
                ndp[j] = max(ndp[j], dp[r + q[head] * W] + (k - q[head]) * Val);
            }
        }
        dp.swap(ndp);
    }
    return dp[V];
}

int main() {
    cout << "朴素      = " << multiNaive() << "\n";
    cout << "二进制拆分 = " << multiBinary() << "\n";   // 三者答案必须一致
    cout << "单调队列   = " << multiDeque() << "\n";
    return 0;
}

（4）分组背包与有依赖的背包（树上背包）

分组背包：物品被分成若干组，每组内最多只能选一件。转移是： dp[j] = max(dp[j], dp[j − w[k]] + v[k])，其中 k 遍历当前组的所有物品， 且容量必须倒序（组内互斥 + 每组只用一次），同时要保证「组内只选一件」—— 做法是先把上一层的 dp 复制一份作为本层的初值，再在组内逐个尝试。 复杂度 O(总物品数 × V)。

有依赖的背包（树上背包）：物品之间有依赖关系（选 A 必须先选 B）， 依赖关系构成一棵树。做法是在树上做 DP：对每个结点 u， 先递归处理所有子结点，然后把子结点当成「分组背包里的一组」合并到 u 上。 典型问题：没有上司的舞会（见 13.5.6）、选课（选一门课必须先选它的先修课）。 复杂度：朴素 O(n·V²)，用「子树大小」限制枚举范围后可优化到 O(n·V)。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

/* ============================================================
   分组背包 + 树上背包（有依赖的背包）
   ============================================================ */
int V = 10;
const int NEG = -1000000000;              // 代表"这个容量不可达"

/* ---------- 分组背包：每组最多选一件 ---------- */
struct Item { int w, v; };
vector<vector<Item>> groups = {
    {{2, 3}, {3, 5}},       // 第 0 组
    {{4, 6}, {5, 8}},       // 第 1 组
    {{3, 4}}                // 第 2 组
};

int groupKnapsack() {
    vector<int> dp(V + 1, 0);
    for (auto& g : groups) {
        for (int j = V; j >= 0; --j)          // ① 倒序容量：保证本组只用一次
            for (auto& it : g)                // ② 组内枚举，选其中一件
                if (j >= it.w)
                    dp[j] = max(dp[j], dp[j - it.w] + it.v);
    }
    return dp[V];
}

/* ---------- 树上背包：选子结点必须先选父结点 ---------- */
int n = 5;
vector<int> cost = {0, 2, 3, 4, 1};       // 下标 1..n
vector<int> val  = {0, 3, 4, 5, 2};
vector<vector<int>> child;
vector<vector<int>> f;                    // f[u][j]：以 u 为根的子树、可用容量 j 的最大价值

void dfs(int u) {
    /* ① 先只考虑"选 u 自己"，此时剩余容量 u→j 对应"用了 j - cost[u] 装子树" */
    f[u].assign(V + 1, NEG);
    f[u][cost[u]] = val[u];
    /* ② 依次把每棵子树当成"一组"，倒序容量合并进来（分组背包的做法） */
    for (int c : child[u]) {
        dfs(c);                                       // 先递归算完子树
        for (int j = V; j >= cost[u]; --j) {           // 倒序：保证 u 自己只被算一次
            if (f[u][j] == NEG) continue;
            for (int k = 0; j + k <= V; ++k)           // 从子树 c 里分配 k 的容量
                if (f[c][k] != NEG)
                    f[u][j + k] = max(f[u][j + k], f[u][j] + f[c][k]);
        }
    }
}

int treeKnapsack() {
    child.assign(n + 1, {});
    child[1] = {2, 3};
    child[2] = {4, 5};
    f.assign(n + 1, {});
    dfs(1);
    int best = 0;
    for (int j = 0; j <= V; ++j) best = max(best, f[1][j] == NEG ? 0 : f[1][j]);
    return best;
}

int main() {
    cout << "分组背包 = " << groupKnapsack() << "\n";        // 13：第0组选(3,5)+第1组选(5,8) = 8
    cout << "树上背包 = " << treeKnapsack() << "\n";         // 9 ：1(2,3) + 2(3,4) + 5(1,2) = 6 ≤ 10
    return 0;
}

（5）方案数背包与「恰好装满」的初始化

前面求的都是「最大价值」，但实际题目里还常常要求「方案数」。这时转移中的 max 要换成加法：

而「恰好装满」与「至多装满」的区别，完全体现在初始化上：

为什么「恰好装满」要初始化成 −∞？因为 −∞ 表示「这个容量无法被恰好凑出」。 如果初始化为 0，那么 dp[j] = 0 会被解释成「装到容量 j 时价值为 0」—— 这既可能是「真的装了价值 0 的东西」，也可能是「什么都没装，容量 j 是虚的」。 两者混在一起，最后算出的答案可能是「不装满但价值更大」的解，与题目要求的「恰好装满」不符。 用 −∞（一个足够小的数）作为「不可达」的标记，就能让非法状态永远无法在 max 中胜出。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int NEG = -1000000000;      // 代表"不可达"

/* ============================================================
   01 背包的四种问法：最大价值（至多/恰好）+ 方案数（至多/恰好）
   初始化的一行之差，决定了答案完全不同
   ============================================================ */
int n = 4, V = 8;
int w[5] = {0, 2, 3, 4, 5};
int v[5] = {0, 3, 4, 5, 6};

/* ① 至多装满的最大价值：全部初始化为 0 */
int maxAtMost() {
    vector<int> dp(V + 1, 0);
    for (int i = 1; i <= n; ++i)
        for (int j = V; j >= w[i]; --j)
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
    return dp[V];
}

/* ② 恰好装满的最大价值：dp[0]=0，其余 -inf */
int maxExactly() {
    vector<int> dp(V + 1, NEG);
    dp[0] = 0;
    for (int i = 1; i <= n; ++i)
        for (int j = V; j >= w[i]; --j)
            if (dp[j - w[i]] != NEG)                     // 只有可达状态才能转移
                dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
    return dp[V] < 0 ? -1 : dp[V];
}

/* ③ 恰好装满的方案数：dp[0]=1，其余 0 */
long long countExactly() {
    vector<long long> dp(V + 1, 0);
    dp[0] = 1;                                            // 空集是一种方案
    for (int i = 1; i <= n; ++i)
        for (int j = V; j >= w[i]; --j)
            dp[j] += dp[j - w[i]];                        // 加法：累加方案数
    return dp[V];
}

/* ④ 完全背包的方案数：正序，dp[0]=1 */
long long countUnbounded() {
    vector<long long> dp(V + 1, 0);
    dp[0] = 1;
    for (int i = 1; i <= n; ++i)
        for (int j = w[i]; j <= V; ++j)                   // 正序：完全背包
            dp[j] += dp[j - w[i]];
    return dp[V];
}

int main() {
    cout << "至多装满最大价值 = " << maxAtMost() << "\n";        // 10
    cout << "恰好装满最大价值 = " << maxExactly() << "\n";       // 10（唯一方案：物品② + 物品④，3+5=8）
    cout << "恰好装满方案数   = " << countExactly() << "\n";     // 1
    cout << "完全背包方案数   = " << countUnbounded() << "\n";   // 5
    return 0;
}

#include <iostream>
#include <vector>
using namespace std;

/* ============================================================
   暴力对拍器：用 DFS 枚举所有方案，验证 DP 的结果
   这是 DP 调试最有效的手段（见 13.5.9）
   ============================================================ */
int w[5] = {0, 2, 3, 4, 5};
int v[5] = {0, 3, 4, 5, 6};
int n = 4, V = 8;
int best = 0;
long long exactCount = 0, exactBest = -1;

/* 01 背包：每件选或不选 */
void dfs01(int i, int cw, int cv) {
    if (i > n) {
        if (cw <= V) best = max(best, cv);            // 至多装满
        if (cw == V) {                                 // 恰好装满
            ++exactCount;
            exactBest = max(exactBest, (long long)cv);
        }
        return;
    }
    if (cw + w[i] <= V) dfs01(i + 1, cw + w[i], cv + v[i]);   // 选
    dfs01(i + 1, cw, cv);                                      // 不选
}

/* 完全背包：每件可以选任意多次 */
long long unboundedCount = 0;
void dfsFull(int i, int cw) {
    if (cw == V) { ++unboundedCount; return; }
    if (i > n) return;
    for (int k = 0; cw + k * w[i] <= V; ++k)
        dfsFull(i + 1, cw + k * w[i]);
}

int main() {
    dfs01(1, 0, 0);
    dfsFull(1, 0);
    cout << "至多装满最大价值 = " << best << "\n";              // 10
    cout << "恰好装满最大价值 = " << exactBest << "\n";        // 10
    cout << "恰好装满方案数   = " << exactCount << "\n";       // 1
    cout << "完全背包方案数   = " << unboundedCount << "\n";   // 5
    return 0;
}

13.5.5 区间 DP：按区间长度从小到大枚举

区间 DP 处理的是「在一个区间 [l, r] 上做决策，决策会把区间劈成两半」的问题。 状态天生是二维的 f[l][r]，转移的方向是「短区间 → 长区间」， 所以遍历顺序必须是：先枚举区间长度 len，再枚举左端点 l，由 len 和 l 算出右端点 r。 这个顺序写错，就会用到还没算出来的值，答案直接错。

（1）矩阵链乘

问题：给定 n 个矩阵 A₁A₂…Aₙ，其中 Aᵢ 的维度是 p[i−1] × p[i]。 矩阵乘法满足结合律，不同的加括号方式会导致标量乘法次数差别巨大，求最少的乘法次数。

状态：m[i][j] = 「计算 AᵢAᵢ₊₁…Aⱼ 所需的最少乘法次数」。 转移：最后一次乘法必然把区间分成 [i, k] 与 [k+1, j] 两部分， 于是 m[i][j] = min over k∈[i, j−1] of ( m[i][k] + m[k+1][j] + p[i−1]·p[k]·p[j] )。 边界 m[i][i] = 0（单个矩阵不用乘）。

修正后的正确表格：

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;

/* ============================================================
   矩阵链乘（区间 DP）
   m[i][j] = 计算 A_i..A_j 的最少乘法次数
   m[i][j] = min over k in [i, j-1] of m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j]
   遍历顺序：len 从 2 到 n（必须！），再枚举左端点
   复杂度：O(n^3)
   ============================================================ */
const int INF = 1000000000;

int main() {
    vector<int> p = {10, 20, 5, 30, 12};      // A_i 的维度是 p[i-1] × p[i]
    int n = p.size() - 1;                     // 矩阵个数 = 4

    vector<vector<int>> m(n + 1, vector<int>(n + 1, 0));
    vector<vector<int>> s(n + 1, vector<int>(n + 1, 0));   // 记录最优切分点，用于还原方案

    for (int len = 2; len <= n; ++len)                    // ① 区间长度递增
        for (int i = 1; i + len - 1 <= n; ++i) {          // ② 左端点
            int j = i + len - 1;                          //    右端点由 len 与 i 决定
            m[i][j] = INF;
            for (int k = i; k < j; ++k) {                 // ③ 枚举切分点
                int cost = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j];
                if (cost < m[i][j]) { m[i][j] = cost; s[i][j] = k; }
            }
        }

    cout << "最少乘法次数 = " << m[1][n] << "\n";            // 3400

    /* 还原最优加括号方案（后序遍历切分点记录） */
    function<void(int,int)> print = [&](int i, int j) {
        if (i == j) { cout << "A" << i; return; }
        cout << "(";
        print(i, s[i][j]);
        print(s[i][j] + 1, j);
        cout << ")";
    };
    print(1, n);
    cout << "\n";     // ((A1A2)(A3A4))
    return 0;
}

（2）石子合并（含环形断环成链）

问题：一排 n 堆石子，每次可以把相邻两堆合并成一堆， 代价是两堆石子数之和，求合并成一堆的最小总代价。

状态：f[i][j] = 「把第 i 堆到第 j 堆合并成一堆的最小代价」。 转移：最后一次合并必然把 [i, j] 分成 [i, k] 与 [k+1, j]， 代价还要加上这两堆合并后的总数（也就是区间和 sum[i][j]）：

其中 sum[i][j] 用前缀和 O(1) 求出： sum[i][j] = pre[j] − pre[i−1]。 边界 f[i][i] = 0。复杂度 O(n³)。

环形版本：如果石子排成一圈（首尾相邻），标准技巧是断环成链—— 把数组复制一份接到后面，长度变成 2n，然后在所有长度为 n 的区间 [1..n], [2..n+1], …, [n..2n−1] 中取最优值。

修正后的正确表格：

下面的动画演示区间 DP 的填表顺序（按区间长度从小到大）并高亮每次转移的来源：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

/* ============================================================
   石子合并（区间 DP）—— 线性版 + 环形版（断环成链）
   f[i][j] = min over k of (f[i][k] + f[k+1][j]) + sum(i..j)
   复杂度 O(n^3)
   ============================================================ */
const int INF = 1000000000;

int linearMerge(const vector<int>& a) {
    int n = a.size();
    vector<int> pre(n + 1, 0);
    for (int i = 1; i <= n; ++i) pre[i] = pre[i - 1] + a[i - 1];

    vector<vector<int>> f(n + 1, vector<int>(n + 1, 0));
    for (int len = 2; len <= n; ++len)                  // ① 区间长度递增（顺序关键）
        for (int i = 1; i + len - 1 <= n; ++i) {        // ② 左端点
            int j = i + len - 1;
            f[i][j] = INF;
            for (int k = i; k < j; ++k)                 // ③ 分割点
                f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j]);
            f[i][j] += pre[j] - pre[i - 1];             // 加上本区间的总石子数
        }
    return f[1][n];
}

int circularMerge(const vector<int>& a) {
    int n = a.size();
    vector<int> b(2 * n + 1, 0);
    for (int i = 1; i <= 2 * n; ++i) b[i] = a[(i - 1) % n];      // 断环成链：复制一份
    vector<int> pre(2 * n + 1, 0);
    for (int i = 1; i <= 2 * n; ++i) pre[i] = pre[i - 1] + b[i];

    vector<vector<int>> f(2 * n + 2, vector<int>(2 * n + 2, 0));
    for (int len = 2; len <= n; ++len)
        for (int i = 1; i + len - 1 <= 2 * n; ++i) {
            int j = i + len - 1;
            f[i][j] = INF;
            for (int k = i; k < j; ++k)
                f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j]);
            f[i][j] += pre[j] - pre[i - 1];
        }

    int best = INF;
    for (int i = 1; i <= n; ++i) best = min(best, f[i][i + n - 1]);   // 所有长度为 n 的区间
    return best;
}

int main() {
    vector<int> a = {4, 1, 3, 2};
    cout << "线性版 = " << linearMerge(a) << "\n";       // 20
    cout << "环形版 = " << circularMerge(a) << "\n";     // 20（本例恰好相同）
    vector<int> c = {1, 2, 3, 4, 5};
    cout << "另一组 线性 = " << linearMerge(c) << "，环形 = " << circularMerge(c) << "\n";
    return 0;
}

13.5.6 树形 DP：在树上做动态规划

树形 DP 的特点：状态定义在结点上，转移沿着父子关系进行， 实现方式是后序遍历（DFS）——先递归算完所有子结点，再用子结点的状态更新父结点。 由于树没有环，「无后效性」天然满足，这是树形 DP 比一般图 DP 好写的原因。

（1）没有上司的舞会

问题：n 个职员构成一棵树（父结点是直接上司），每个职员有快乐值 h[i]。 选若干人参加舞会，要求不能同时选一个人和他的直接上司，求最大总快乐值。

状态：对每个结点 u 定义两个状态：

• dp[u][0]：不选 u 时，以 u 为根的子树能取得的最大快乐值；
• dp[u][1]：选 u 时，以 u 为根的子树能取得的最大快乐值。

转移：

答案：max(dp[root][0], dp[root][1])。复杂度 O(n)（每个结点只被访问一次）。

#include <iostream>
#include <vector>
#include <array>
#include <algorithm>
using namespace std;

/* ============================================================
   没有上司的舞会（树形 DP）
   dp[u][0]：不选 u 时子树最大快乐值
   dp[u][1]：选 u 时子树最大快乐值
   转移：dp[u][0] = Σ max(dp[v][0], dp[v][1])
         dp[u][1] = h[u] + Σ dp[v][0]
   时间 O(n)
   ============================================================ */
int n = 5;
vector<int> h = {0, 5, 4, 3, 2, 3};        // 下标 1..n
vector<vector<int>> child;
vector<array<int,2>> dp;

void dfs(int u) {
    dp[u][0] = 0;
    dp[u][1] = h[u];
    for (int v : child[u]) {
        dfs(v);                             // 先算子树（后序）
        dp[u][0] += max(dp[v][0], dp[v][1]);   // 不选 u：子结点随意
        dp[u][1] += dp[v][0];                  // 选 u：子结点不能选
    }
}

int main() {
    child.assign(n + 1, {});
    child[1] = {2, 3};
    child[2] = {4, 5};
    dp.assign(n + 1, {0, 0});
    dfs(1);                                 // 1 号是根（没有上司的人）
    cout << "最大快乐值 = " << max(dp[1][0], dp[1][1]) << "\n";   // 10
    cout << "dp[1][0] = " << dp[1][0] << "，dp[1][1] = " << dp[1][1] << "\n";  // 8, 10
    return 0;
}

（2）树的直径

问题：求树上最远两个点之间的距离（边数或边权和）。

两种经典解法，都要会：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

/* ============================================================
   树的直径：两次 DFS 版 + 树形 DP 版
   ============================================================ */
int n = 6;
vector<vector<pair<int,int>>> g;          // (邻点, 边权)

/* ---------- 解法一：两次 DFS ---------- */
void dfsFar(int u, int fa, int d, int& farNode, int& farDist) {
    if (d > farDist) { farDist = d; farNode = u; }
    for (auto& e : g[u])
        if (e.first != fa) dfsFar(e.first, u, d + e.second, farNode, farDist);
}

int diameterTwoDfs() {
    int a = 1, d1 = -1;
    dfsFar(1, 0, 0, a, d1);                 // 第一次：从 1 出发找最远点 a
    int b = a, d2 = -1;
    dfsFar(a, 0, 0, b, d2);                 // 第二次：从 a 出发找最远点 b
    return d2;                              // dist(a, b) 即直径
}

/* ---------- 解法二：树形 DP ---------- */
int best = 0;
int dfsDown(int u, int fa) {
    int mx1 = 0, mx2 = 0;                   // 最长的两条向下的链
    for (auto& e : g[u]) {
        if (e.first == fa) continue;
        int d = dfsDown(e.first, u) + e.second;
        if (d > mx1) { mx2 = mx1; mx1 = d; }
        else if (d > mx2) { mx2 = d; }
    }
    best = max(best, mx1 + mx2);            // 以 u 为"最高点"的路径
    return mx1;
}

int diameterTreeDp() {
    best = 0;
    dfsDown(1, 0);
    return best;
}

int main() {
    g.assign(n + 1, {});
    auto add = [](int u, int v, int w) { g[u].push_back({v, w}); g[v].push_back({u, w}); };
    add(1, 2, 3); add(1, 3, 1); add(2, 4, 2); add(2, 5, 4); add(3, 6, 5);

    cout << "两次 DFS 求直径 = " << diameterTwoDfs() << "\n";     // 14（路径 5-2-1-3-6：4+3+1+5）
    cout << "树形 DP 求直径   = " << diameterTreeDp() << "\n";    // 14
    return 0;
}

13.5.7 状压 DP：用二进制表示集合

当状态里包含「一个集合」时（例如「已经访问过哪些城市」「这一行哪些位置放了东西」）， 如果 n 不大（一般 n ≤ 20），我们可以用一个整数的二进制位来表示这个集合—— 第 i 位为 1 表示元素 i 在集合里。这就是状态压缩（state compression）。

常用位运算速查（必须熟练到不用想）：

（1）旅行商问题 TSP

问题：n 个城市两两之间有权值 dist[i][j]，从城市 0 出发， 每个城市恰好访问一次，最后回到城市 0，求最小总路程。

状态：dp[mask][i] = 「已访问的城市集合是 mask，且当前停在城市 i」时的最小路程。 注意 mask 里一定包含 i。 转移：dp[mask | (1<<j)][j] = min(dp[mask][i] + dist[i][j])，其中 j ∉ mask。 初始化：dp[1][0] = 0（只访问了城市 0，就在城市 0），其余为 +∞。 答案：min over i of ( dp[(1<<n)−1][i] + dist[i][0] )。 复杂度：O(2ⁿ · n²)，空间 O(2ⁿ · n)。

验证最优路径 0 → 3 → 2 → 1 → 0：20 + 30 + 35 + 10 = 95； 路径 0 → 1 → 3 → 2 → 0：10 + 25 + 30 + 15 = 80； 路径 0 → 1 → 2 → 3 → 0：10 + 35 + 30 + 20 = 95； 路径 0 → 2 → 1 → 3 → 0：15 + 35 + 25 + 20 = 95； 路径 0 → 2 → 3 → 1 → 0：15 + 30 + 25 + 10 = 80； 路径 0 → 3 → 1 → 2 → 0：20 + 25 + 35 + 15 = 95。 最小值是 80，有两条最优回路（互为反向）。

下面的动画逐帧展示 dp[mask][i] 的转移过程：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

/* ============================================================
   TSP（旅行商问题）· 状压 DP
   dp[mask][i] = 已访问集合为 mask、当前在城市 i 的最小路程
   转移：dp[mask | (1<<j)][j] = min(dp[mask][i] + dist[i][j])，j 不在 mask 中
   复杂度：时间 O(2^n · n^2)，空间 O(2^n · n)
   ============================================================ */
const int INF = 1000000000;

int main() {
    int n = 4;
    int dist[4][4] = {
        { 0, 10, 15, 20},
        {10,  0, 35, 25},
        {15, 35,  0, 30},
        {20, 25, 30,  0}
    };
    int FULL = (1 << n) - 1;

    vector<vector<int>> dp(1 << n, vector<int>(n, INF));
    vector<vector<int>> pre(1 << n, vector<int>(n, -1));   // 记录前驱，用于还原路径
    dp[1][0] = 0;                                        // 只访问了城市 0，位于城市 0

    for (int mask = 1; mask <= FULL; ++mask) {
        for (int i = 0; i < n; ++i) {
            if (dp[mask][i] == INF) continue;            // 该状态不可达
            if (!((mask >> i) & 1)) continue;            // i 必须在 mask 中
            for (int j = 0; j < n; ++j) {
                if ((mask >> j) & 1) continue;           // j 不能在 mask 中
                int nmask = mask | (1 << j);
                int nd = dp[mask][i] + dist[i][j];
                if (nd < dp[nmask][j]) { dp[nmask][j] = nd; pre[nmask][j] = i; }
            }
        }
    }

    int ans = INF, last = -1;
    for (int i = 0; i < n; ++i)
        if (dp[FULL][i] + dist[i][0] < ans) { ans = dp[FULL][i] + dist[i][0]; last = i; }
    cout << "最短回路长度 = " << ans << "\n";               // 80
    /* 注意：也可以把 dp 的维度反过来写成 dp[1<<n][n]，先把所有状态算完； */

    /* ---------- 还原路径 ---------- */
    vector<int> path;
    int mask = FULL, cur = last;
    while (cur != -1) {
        path.push_back(cur);
        int p = pre[mask][cur];
        mask ^= (1 << cur);                              // 去掉当前城市
        cur = p;
    }
    reverse(path.begin(), path.end());
    cout << "路径：0";
    for (int v : path) if (v != 0) cout << " -> " << v;
    cout << " -> 0\n";                                   // 0 -> 1 -> 3 -> 2 -> 0
    return 0;
}

（2）蒙德里安的梦想（铺砖问题）与枚举子集技巧

问题：用 1×2 的多米诺骨牌铺满 N × M 的棋盘，求方案数。

状态的巧妙之处：我们按列处理，用 f[i][j] 表示 「前 i−1 列已经铺满，且第 i 列有 j 这个「突出状态」的方案数」。 这里的 j 是一个 N 位的二进制数，第 k 位为 1 表示第 i 列的第 k 行有一个 横着放、伸到第 i+1 列的骨牌（也就是「突出到右边」）。

合法性判断的核心是：第 i 列被竖着放的骨牌和从第 i−1 列伸过来的骨牌占完后， 剩下的连续空位必须是偶数长度（否则无法用竖着的 1×2 骨牌填满）。 于是可以预处理出所有「自身连续空位为偶数」的合法 mask，记作 st[mask]。

答案 f[M][0]（第 M 列不能有任何突出的骨牌，因为棋盘已经结束）。 复杂度 O(M · 4^N)（两两枚举 mask），用「枚举合法子集」的技巧可以优化到 O(M · 3^N)。

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

/* ============================================================
   蒙德里安的梦想：N×M 棋盘用 1×2 骨牌铺满的方案数
   状态压缩 DP：f[i][j] = 前 i-1 列铺满、第 i 列"突出状态"为 j 的方案数
   复杂度 O(M · 4^N)，N ≤ 11、M ≤ 11 时可接受
   ============================================================ */
const int MAXM = 12;
long long f[MAXM][1 << MAXM];
bool st[1 << MAXM];

int main() {
    int N = 2, M = 3;                       // 2 × 3 棋盘，答案应为 3
    int FULL = 1 << N;

    /* 预处理：哪些 mask 的"连续空位"长度全为偶数 */
    for (int mask = 0; mask < FULL; ++mask) {
        int cnt = 0;                        // 当前连续 0 的个数
        bool ok = true;
        for (int k = 0; k < N; ++k) {
            if ((mask >> k) & 1) {          // 遇到 1，结算前面的连续 0
                if (cnt & 1) { ok = false; break; }
                cnt = 0;
            } else ++cnt;
        }
        if (cnt & 1) ok = false;            // 末尾的连续 0 也要是偶数
        st[mask] = ok;
    }

    memset(f, 0, sizeof(f));
    f[0][0] = 1;                            // 第 0 列没有任何突出
    for (int i = 1; i <= M; ++i) {           // 枚举列
        for (int j = 0; j < FULL; ++j) {     // 本列的突出状态
            for (int k = 0; k < FULL; ++k) { // 上一列伸过来的状态
                if ((j & k) == 0 && st[j | k])   // 不能同行冲突；合并后空位必须是偶数
                    f[i][j] += f[i - 1][k];
            }
        }
    }
    cout << N << " x " << M << " 棋盘的方案数 = " << f[M][0] << "\n";   // 3

    /* ---------- 枚举子集技巧：把一个 mask 拆成两部分 ---------- */
    /* 例题风格：dp[S] = min over T ⊂ S of dp[T] + cost(S \ T)
       朴素枚举是 O(4^n)，用 (t-1)&s 枚举子集降到 O(3^n) */
    int n = 4;
    for (int s = 1; s < (1 << n); ++s) {
        /* 枚举 s 的所有非空真子集 t */
        for (int t = s; t; t = (t - 1) & s) {
            /* 这里写 dp[s] = min(dp[s], dp[t] + dp[s ^ t]) 之类的转移 */
            (void)t;
        }
    }
    cout << "枚举子集的总枚举次数 = 3^" << n << " = " << [] {
        int c = 0, n = 4;
        for (int s = 0; s < (1 << n); ++s)
            for (int t = s; ; t = (t - 1) & s) { ++c; if (t == 0) break; }
        return c;
    }() << "（含空集，恰好等于 3^n）\n";
    return 0;
}

13.5.8 DP 的优化技巧汇总

写出一份正确的 DP 只是第一步，能不能过题还取决于时空复杂度。下面五类优化按「常用度」排序。

关于斜率优化的形式判定：如果转移方程整理后能得到

其中 a[i] 只与 i 有关、b[j] 与 d[j] 只与 j 有关， 那么就可以把「每个 j」看作平面上的点 ( b[j], dp[j] + d[j] )， 转移就是在这些点中找一条斜率为 −a[i] 的直线所截的最小截距。 若 a[i] 单调，用单调队列维护凸壳即可 O(n)； 若 a[i] 不单调，需要在凸壳上二分，O(n log n)。 判定口诀：出现「i 与 j 的乘积项」就考虑斜率优化。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

/* ============================================================
   单调队列优化 DP 示例
   问题：给定数组 a[1..n]，选若干个数，要求任意两个被选的数下标差不超过 k，
        问能否选到最后一个数（或求最小代价）。
   这里给出更典型的「滑动窗口最小值」形式：
        dp[i] = min(dp[j]) + a[i]，其中 i - k <= j < i
   ============================================================ */
int main() {
    int n = 8, k = 3;
    vector<int> a = {0, 1, 3, 2, 4, 1, 5, 2, 3};        // 下标 1..8
    const int INF = 1000000000;
    vector<int> dp(n + 1, INF);
    dp[0] = 0;

    vector<int> q(n + 2);                                 // 单调队列存下标
    int head = 0, tail = 0;
    q[tail++] = 0;                                        // 先把 dp[0] 入队
    for (int i = 1; i <= n; ++i) {
        while (head < tail && q[head] < i - k) ++head;     // ① 弹出窗口外的
        dp[i] = dp[q[head]] + a[i];                       // ② 队首就是窗口内最小值
        while (head < tail && dp[q[tail - 1]] >= dp[i]) --tail;   // ③ 保持单调递增
        q[tail++] = i;
    }
    cout << "dp = ";
    for (int i = 0; i <= n; ++i) cout << dp[i] << ' ';
    cout << "\n";
    /* 复杂度：每个下标最多入队一次、出队一次 → 总时间 O(n) */
    return 0;
}

#include <iostream>
#include <vector>
using namespace std;

/* ============================================================
   矩阵快速幂求斐波那契第 n 项（n 可达 10^18）
   [f(n+1)]   [1 1]^n   [f(1)]
   [f(n)  ] = [1 0]   × [f(0)]
   复杂度 O(log n)
   ============================================================ */
const long long MOD = 1000000007LL;

struct Mat {
    long long a[2][2];
    Mat() { a[0][0] = a[0][1] = a[1][0] = a[1][1] = 0; }
    static Mat identity() { Mat m; m.a[0][0] = m.a[1][1] = 1; return m; }
};

Mat mul(const Mat& x, const Mat& y) {
    Mat r;
    for (int i = 0; i < 2; ++i)
        for (int k = 0; k < 2; ++k)
            if (x.a[i][k])
                for (int j = 0; j < 2; ++j)
                    r.a[i][j] = (r.a[i][j] + x.a[i][k] * y.a[k][j]) % MOD;
    return r;
}

Mat power(Mat base, long long e) {
    Mat r = Mat::identity();
    while (e > 0) {
        if (e & 1) r = mul(r, base);
        base = mul(base, base);
        e >>= 1;
    }
    return r;
}

int main() {
    long long n = 90;
    Mat M;
    M.a[0][0] = 1; M.a[0][1] = 1; M.a[1][0] = 1; M.a[1][1] = 0;
    Mat P = power(M, n);
    cout << "fib(" << n << ") mod 1e9+7 = " << P.a[0][1] % MOD << "\n";
    /* fib(90) = 2880067194370816120，取模后为 2880067194370816120 % 1000000007 = 466004661 */
    cout << "log 级别：n = 10^18 也只需约 60 次矩阵乘法\n";
    return 0;
}

13.5.9 DP 的调试方法：三个动作救命

写 DP 最痛苦的体验是「样例过了，交上去 WA」。因为 DP 的错误往往是静默的： 初始化错了一个值、循环方向反了、答案取错了位置——程序照样跑得飞快，就是答案不对。 下面三个动作能解决 90% 的 DP bug。

#include <iostream>
#include <vector>
#include <cstdlib>
#include <algorithm>
using namespace std;

/* ============================================================
   DP 调试三件套：打印 dp 表 / 随机对拍 / 边界自测
   ============================================================ */

/* ---- 待测的 DP（以 01 背包为例） ---- */
int dpSolve(int n, int V, const vector<int>& w, const vector<int>& v, bool dump) {
    vector<vector<int>> dp(n + 1, vector<int>(V + 1, 0));
    for (int i = 1; i <= n; ++i)
        for (int j = 0; j <= V; ++j) {
            dp[i][j] = dp[i - 1][j];
            if (j >= w[i]) dp[i][j] = max(dp[i][j], dp[i - 1][j - w[i]] + v[i]);
        }
    if (dump) {                                  /* ① 打印 dp 表 */
        cout << "    j:";
        for (int j = 0; j <= V; ++j) cout << " " << j;
        cout << "\n";
        for (int i = 0; i <= n; ++i) {
            cout << "i=" << i << " :";
            for (int j = 0; j <= V; ++j) cout << " " << dp[i][j];
            cout << "\n";
        }
    }
    return dp[n][V];
}

/* ---- 暴力：枚举所有子集 ---- */
int bruteSolve(int n, int V, const vector<int>& w, const vector<int>& v) {
    int best = 0;
    for (int mask = 0; mask < (1 << n); ++mask) {
        int cw = 0, cv = 0;
        for (int i = 0; i < n; ++i)
            if (mask >> i & 1) { cw += w[i + 1]; cv += v[i + 1]; }
        if (cw <= V) best = max(best, cv);
    }
    return best;
}

int main() {
    srand(12345);
    /* ---------- ② 随机对拍 ---------- */
    for (int test = 1; test <= 500; ++test) {
        int n = rand() % 8 + 1;                 // 1..8 件物品
        int V = rand() % 15 + 1;                // 容量 1..15
        vector<int> w(n + 1), v(n + 1);
        for (int i = 1; i <= n; ++i) { w[i] = rand() % 8 + 1; v[i] = rand() % 20 + 1; }

        int a = dpSolve(n, V, w, v, false);
        int b = bruteSolve(n, V, w, v);
        if (a != b) {
            cout << "对拍失败！n=" << n << " V=" << V << "　DP=" << a << " 暴力=" << b << "\n";
            cout << "物品：";
            for (int i = 1; i <= n; ++i) cout << "(" << w[i] << "," << v[i] << ") ";
            cout << "\n";
            dpSolve(n, V, w, v, true);          // 打印出错的 dp 表
            return 1;
        }
    }
    cout << "500 组随机数据全部通过 ✓\n";

    /* ---------- ③ 边界自测 ---------- */
    vector<int> w1 = {0, 5}, v1 = {0, 7};
    cout << "n=1,V=5  → " << dpSolve(1, 5, w1, v1, false) << "（应为 7）\n";
    cout << "n=1,V=4  → " << dpSolve(1, 4, w1, v1, false) << "（应为 0，装不下）\n";
    cout << "n=1,V=0  → " << dpSolve(1, 0, w1, v1, false) << "（应为 0，容量为 0）\n";
    return 0;
}

13.6 数学类算法

算法竞赛里有一大类题目，它的难点不在「设计范式」，而在于数学结论 + 模板代码： 数论、组合数学、快速幂、高精度、博弈论……这一节的定位是模板手册： 每个算法给出结论、完整 C++ 实现和验证用例，方便你考试前直接背。 本节内容与范式的关系是：快速幂是「减治」（指数规模不断减半），筛法是「预处理换查询」， 二分/三分是「减治」，而矩阵快速幂本质上是「用矩阵乘法把一个线性 DP 的转移加速」—— 回头再看 13.5.8，你会对「DP 优化」有更完整的认识。

13.6.1 数论基础：gcd、lcm、扩展欧几里得与裴蜀定理

（1）最大公约数：欧几里得与更相减损

两种求 gcd 的方法，都出自中国古代与古希腊的数学遗产：

欧几里得算法（辗转相除）

gcd(a, b) = gcd(b, a mod b)，gcd(a, 0) = a。 每次把较大的数换成「它除以较小数的余数」，余数下降极快（至少减半）， 所以复杂度是 O(log min(a,b))。
为什么对？因为 d | a 且 d | b ⟺ d | b 且 d | (a − kb)， 取 k = ⌊a/b⌋ 即得 gcd(a,b) = gcd(b, a mod b)。

更相减损术（中国古代《九章算术》）

反复用大数减小数：gcd(a, b) = gcd(a − b, b)（a > b）。 正确性同样来自上面的性质（取 k = 1），但减法比取模慢得多—— 当 a = 10⁹, b = 1 时要减 10 亿次。 所以工程中一律用欧几里得；更相减损术只在「大整数取模极慢」的场合（如高精度）才有优势。

（2）最小公倍数与溢出陷阱

注意先除后乘！如果写成 a * b / gcd(a, b)， 当 a = b = 10⁹ 时 a × b = 10¹⁸ 还没溢出 long long， 但若 a、b 更大（例如都是 10¹⁸），乘法就先溢出了。 先除以 gcd 再乘，中间结果一定不超过 lcm(a,b)，安全得多。

（3）扩展欧几里得与裴蜀定理

裴蜀定理（Bézout's identity，也叫贝祖定理）： 对任意整数 a、b（不全为 0），存在整数 x、y 使得

并且 a·x + b·y 能取到的最小正整数恰好就是 gcd(a, b)。 推论：a·x + b·y = c 有整数解当且仅当 gcd(a,b) | c。

扩展欧几里得算法（exgcd）就是求这组 (x, y) 的算法。 思路：递归到 gcd(b, a mod b) 得到 b·x' + (a mod b)·y' = g， 再把 a mod b = a − ⌊a/b⌋·b 代回去整理：

#include <iostream>
using namespace std;

/* ============================================================
   数论基础：欧几里得 / 更相减损 / lcm / 扩展欧几里得 / 裴蜀定理
   ============================================================ */

/* ---------- 欧几里得算法（辗转相除），O(log min(a,b)) ---------- */
long long gcd_euclid(long long a, long long b) {
    while (b) { long long t = a % b; a = b; b = t; }
    return a;
}
/* 递归写法（更贴近定义） */
long long gcd_rec(long long a, long long b) {
    return b == 0 ? a : gcd_rec(b, a % b);
}

/* ---------- 更相减损术（《九章算术》），最坏 O(max(a,b)) ---------- */
long long gcd_subtract(long long a, long long b) {
    while (a != b) {
        if (a > b) a -= b; else b -= a;
    }
    return a;
}

/* ---------- 最小公倍数：先除后乘，防止溢出 ---------- */
long long lcm(long long a, long long b) {
    return a / gcd_euclid(a, b) * b;
}

/* ---------- 扩展欧几里得：求 a*x + b*y = gcd(a,b) 的一组解 ---------- */
long long exgcd(long long a, long long b, long long& x, long long& y) {
    if (b == 0) { x = 1; y = 0; return a; }
    long long g = exgcd(b, a % b, y, x);       // 注意这里 x、y 传参顺序交换
    y -= (a / b) * x;                          // 对应公式 y = x' - (a/b)*y'
    return g;
}

int main() {
    cout << "gcd(30,18)  欧几里得 = " << gcd_euclid(30, 18) << "\n";      // 6
    cout << "gcd(30,18)  递归     = " << gcd_rec(30, 18) << "\n";         // 6
    cout << "gcd(30,18)  更相减损 = " << gcd_subtract(30, 18) << "\n";    // 6
    cout << "lcm(12,18) = " << lcm(12, 18) << "\n";                     // 36

    long long x, y;
    long long g = exgcd(30, 18, x, y);
    cout << "exgcd(30,18): g = " << g << ", x = " << x << ", y = " << y << "\n";
    cout << "验证：30*" << x << " + 18*" << y << " = " << 30 * x + 18 * y << "\n";
    /* 递归展开：exgcd(30,18) → exgcd(18,12) → exgcd(12,6) → exgcd(6,0)
       回溯得到 x = -1, y = 2，验证 -30 + 36 = 6 = gcd ✓ */

    /* 裴蜀定理应用：判断 a*x + b*y = c 是否有整数解 */
    long long c = 15;
    cout << "30x + 18y = " << c << (c % g == 0 ? " 有解" : " 无解") << "\n";    // 有解（15 % 6 != 0 → 无解）
    return 0;
}

13.6.2 同余、逆元与中国剩余定理

同余：若 a mod m == b mod m，记作 a ≡ b (mod m)。同余式可以加减乘，但不能随便除——这正是逆元存在的意义。

乘法逆元（modular inverse）：若 a·x ≡ 1 (mod m)，称 x 是 a 在模 m 下的逆元，记作 a⁻¹。 存在逆元的充要条件是 gcd(a, m) = 1。 有了逆元，a/b (mod m) 就可以写成 a · b⁻¹ (mod m)，除法就变成了乘法。

两种求法，都要会：

方法一：费马小定理（要求 m 是质数）

费马小定理：若 p 为质数且 p ∤ a，则 a^(p−1) ≡ 1 (mod p)。 两边同乘 a⁻¹ 得 a⁻¹ ≡ a^(p−2) (mod p)。 于是用快速幂求 a^(p−2) mod p 即可，复杂度 O(log p)。
缺点：只能用于质数模数。实战中常用的 998244353、10⁹+7 都是质数，所以这招最常用。

方法二：扩展欧几里得（任意模数，只要互质）

解同余方程 a·x ≡ 1 (mod m) 等价于解 a·x + m·y = 1。 直接套 exgcd，得到 x 后取 (x % m + m) % m 化为最小正整数即可。
优点：模数不必是质数，只要 gcd(a,m)=1。复杂度同样是 O(log m)。

中国剩余定理（CRT）：求解同余方程组 x ≡ a₁ (mod m₁), x ≡ a₂ (mod m₂), …, x ≡ aₖ (mod mₖ)， 其中模数两两互质。结论：在 [0, M)（M = Πmᵢ）内解唯一，可以显式构造。

#include <iostream>
using namespace std;

/* ============================================================
   快速幂 / 费马小定理求逆元 / exgcd 求逆元 / 中国剩余定理
   ============================================================ */

/* ---------- 快速幂：a^e mod mod，O(log e) ---------- */
long long qpow(long long a, long long e, long long mod) {
    long long r = 1 % mod;
    a %= mod;
    while (e > 0) {
        if (e & 1) r = r * a % mod;
        a = a * a % mod;
        e >>= 1;
    }
    return r;
}

long long exgcd(long long a, long long b, long long& x, long long& y) {
    if (b == 0) { x = 1; y = 0; return a; }
    long long g = exgcd(b, a % b, y, x);
    y -= (a / b) * x;
    return g;
}

/* ---------- 方法一：费马小定理（mod 必须是质数） ---------- */
long long invFermat(long long a, long long mod) {
    return qpow(a, mod - 2, mod);
}

/* ---------- 方法二：扩展欧几里得（gcd(a,mod)=1 即可） ---------- */
long long invExgcd(long long a, long long mod) {
    long long x, y;
    exgcd(a, mod, x, y);
    return (x % mod + mod) % mod;              // 化为最小正整数
}

/* ---------- 中国剩余定理（模数两两互质） ---------- */
long long crt(const long long a[], const long long m[], int k) {
    long long M = 1;
    for (int i = 0; i < k; ++i) M *= m[i];
    long long ans = 0;
    for (int i = 0; i < k; ++i) {
        long long Mi = M / m[i];
        long long inv = invExgcd(Mi % m[i], m[i]);   // Mi 在模 m[i] 下的逆元
        ans = (ans + a[i] * Mi % M * inv) % M;
    }
    return (ans % M + M) % M;
}

int main() {
    cout << "2^10 mod 1000 = " << qpow(2, 10, 1000) << "\n";        // 24
    cout << "3 在模 11 下的逆元：费马 = " << invFermat(3, 11)
         << "，exgcd = " << invExgcd(3, 11) << "\n";                 // 4，4
    cout << "验证 3*4 mod 11 = " << (3 * 4) % 11 << "\n";          // 1
    cout << "7 在模 26 下的逆元 = " << invExgcd(7, 26) << "\n";     // 15（7*15 = 105 = 4*26+1）

    /* CRT 实例：x ≡ 2 (mod 3)，x ≡ 3 (mod 5)，x ≡ 2 (mod 7) */
    long long a[3] = {2, 3, 2};
    long long m[3] = {3, 5, 7};
    cout << "CRT 解 = " << crt(a, m, 3) << "\n";                   // 23
    /* 验证：23 mod 3 = 2 ✓，23 mod 5 = 3 ✓，23 mod 7 = 2 ✓，M = 105 */
    return 0;
}

13.6.3 欧拉函数与线性筛

欧拉函数 φ(n)：小于等于 n 且与 n 互质的正整数个数。 若 n = p₁^a₁ · p₂^a₂ · … · pₖ^aₖ（质因数分解），则

特例：φ(1) = 1；φ(p) = p − 1（p 为质数）；φ(p^k) = p^k − p^(k−1)。 欧拉函数是积性函数：当 gcd(a,b)=1 时 φ(ab) = φ(a)·φ(b)—— 这个性质是线性筛能顺带求出 φ 的关键。

欧拉定理：若 gcd(a, n) = 1，则 a^φ(n) ≡ 1 (mod n)。 费马小定理就是 n 为质数时的特例（此时 φ(n) = n − 1）。

13.6.4 质数筛法：埃氏筛与欧拉线性筛

线性筛的核心代码只有几行，但必须理解 break 那一句：

#include <iostream>
#include <vector>
using namespace std;

/* ============================================================
   质数筛法：埃氏筛 O(n log log n) / 欧拉线性筛 O(n)
   线性筛顺便求出：最小质因子 minp[]、欧拉函数 phi[]
   ============================================================ */
const int N = 100;

/* ---------- 埃氏筛 ---------- */
vector<bool> esieve(int n) {
    vector<bool> isPrime(n + 1, true);
    isPrime[0] = isPrime[1] = false;
    for (int i = 2; (long long)i * i <= n; ++i)          // 只需筛到 sqrt(n)
        if (isPrime[i])
            for (int j = i * i; j <= n; j += i)          // 从 i*i 开始，前面的已被更小的质数筛过
                isPrime[j] = false;
    return isPrime;
}

/* ---------- 欧拉线性筛：每个合数只被最小质因子筛一次 ---------- */
vector<int> primes;
vector<int> minp;          // minp[i] = i 的最小质因子
vector<int> phi;           // phi[i] = 欧拉函数值

void linearSieve(int n) {
    minp.assign(n + 1, 0);
    phi.assign(n + 1, 0);
    primes.clear();
    phi[1] = 1;
    for (int i = 2; i <= n; ++i) {
        if (minp[i] == 0) {                    // i 没有被筛过 → i 是质数
            minp[i] = i;
            phi[i] = i - 1;                    // 质数的 φ = p - 1
            primes.push_back(i);
        }
        for (int p : primes) {
            if ((long long)p * i > n) break;   // 超出范围
            minp[p * i] = p;                   // p 是 p*i 的最小质因子（因为 p ≤ minp[i]）
            if (i % p == 0) {                  // ★ 关键：p 已经是 i 的最小质因子
                phi[p * i] = phi[i] * p;       //   此时 φ(i*p) = φ(i) * p
                break;                         //   break 保证每个合数只被筛一次
            } else {
                phi[p * i] = phi[i] * (p - 1); // p 与 i 互质 → 积性：φ(i*p) = φ(i)*(p-1)
            }
        }
    }
}

int main() {
    vector<bool> isP = esieve(N);
    cout << "埃氏筛 100 以内质数：";
    for (int i = 2; i <= N; ++i) if (isP[i]) cout << i << ' ';
    cout << "\n";

    linearSieve(N);
    cout << "线性筛质数个数 = " << primes.size() << "\n";
    cout << "minp[12] = " << minp[12] << "（12 = 2²×3，最小质因子是 2）\n";
    cout << "phi[12] = " << phi[12] << "（与 12 互质的有 1,5,7,11，共 4 个）\n";
    cout << "phi[1..10] = ";
    for (int i = 1; i <= 10; ++i) cout << phi[i] << ' ';
    cout << "\n";     // 1 1 2 2 4 2 6 4 6 4

    /* 用 minp 做 O(log n) 质因数分解 */
    int x = 60;
    cout << x << " = ";
    while (x > 1) {
        int p = minp[x], c = 0;
        while (x % p == 0) { x /= p; ++c; }
        cout << p << "^" << c << (x > 1 ? " × " : "");
    }
    cout << "\n";     // 2^2 × 3^1 × 5^1
    return 0;
}

13.6.5 快速幂与矩阵快速幂

快速幂的思想是「把指数二进制拆分」：a^13 = a^(1101₂) = a^8 · a^4 · a^1。 我们从低位到高位，不断把底数平方（得到 a^1, a^2, a^4, a^8, …）， 指数当前位为 1 就把对应的幂乘进答案。复杂度 O(log e)。

矩阵快速幂把同样的思想用在矩阵上：如果递推关系能写成 V(n) = M · V(n−1)（V 是状态向量，M 是常数矩阵）， 那么 V(n) = Mⁿ · V(0)，而 Mⁿ 可以用快速幂在 O(k³ log n) 内求出 （k 是矩阵阶数）。这是处理「n 达到 10¹⁸ 的线性递推」的唯一通用手段。

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

/* ============================================================
   通用矩阵快速幂（k 阶方阵）+ 斐波那契第 n 项
   复杂度 O(k^3 log n)
   ============================================================ */
const int K = 3;
const long long MOD = 1000000007LL;

struct Mat {
    long long a[K][K];
    Mat() { memset(a, 0, sizeof(a)); }
    static Mat identity() {
        Mat m;
        for (int i = 0; i < K; ++i) m.a[i][i] = 1;
        return m;
    }
};

Mat mul(const Mat& x, const Mat& y) {
    Mat r;
    for (int i = 0; i < K; ++i)
        for (int k = 0; k < K; ++k) {
            if (x.a[i][k] == 0) continue;                 // 稀疏优化
            for (int j = 0; j < K; ++j)
                r.a[i][j] = (r.a[i][j] + x.a[i][k] * y.a[k][j]) % MOD;
        }
    return r;
}

Mat matPow(Mat base, long long e) {
    Mat r = Mat::identity();
    while (e > 0) {
        if (e & 1) r = mul(r, base);
        base = mul(base, base);
        e >>= 1;
    }
    return r;
}

int main() {
    /* ---------- 斐波那契：用 2 阶矩阵 ---------- */
    /* [f(n+1)]   [1 1]^n   [f(1)]     f(1) = f(2) = 1
       [f(n)  ] = [1 0]   × [f(0)]     这里取 f(0) = 1, f(1) = 1（错位一项） */
    long long n = 90;
    Mat M;
    M.a[0][0] = 1; M.a[0][1] = 1; M.a[0][2] = 0;
    M.a[1][0] = 1; M.a[1][1] = 0; M.a[1][2] = 0;
    M.a[2][0] = 0; M.a[2][1] = 0; M.a[2][2] = 1;     // 第三维留作占位，方便演示 3 阶
    Mat P = matPow(M, n - 1);
    cout << "fib(" << n << ") mod 1e9+7 = " << (P.a[0][0] + P.a[0][1]) % MOD << "\n";

    /* ---------- 经典应用：走方格方案数 ---------- */
    /* 每次可以走 1 步或 2 步，从 0 走到 n 的方案数 = fib(n+1)
       转移：f[i] = f[i-1] + f[i-2]  →  同一个矩阵 */
    cout << "走 10 级台阶的方案数 = " << (matPow(M, 10).a[0][0] + matPow(M, 10).a[0][1]) % MOD << "\n";   // 89

    /* ---------- 三阶递推示例：f(n) = f(n-1) + f(n-2) + f(n-3) ---------- */
    Mat T;
    T.a[0][0] = 1; T.a[0][1] = 1; T.a[0][2] = 1;
    T.a[1][0] = 1; T.a[1][1] = 0; T.a[1][2] = 0;
    T.a[2][0] = 0; T.a[2][1] = 1; T.a[2][2] = 0;
    /* 初值 f(0)=f(1)=1, f(2)=2（泰波那契数列的变体），求 f(10) */
    Mat Q = matPow(T, 8);                    // 从 f(2) 推到 f(10) 需 8 步
    long long f10 = (Q.a[0][0] * 2 + Q.a[0][1] * 1 + Q.a[0][2] * 1) % MOD;
    cout << "泰波那契式递推 f(10) = " << f10 << "\n";        // 手算应为 274
    return 0;
}

13.6.6 组合数学

组合数学在竞赛中出现的频率极高，下面把常用公式与三种求组合数的方法一次讲清。

三种求法，按数据规模选：

#include <iostream>
#include <vector>
using namespace std;

/* ============================================================
   组合数三种求法 + 卡特兰数 + 卢卡斯定理
   ============================================================ */
const long long MOD = 1000000007LL;         // 质数
const int MAXN = 2000;

/* ---------- ① 杨辉三角递推：C(n,m) = C(n-1,m-1) + C(n-1,m)，O(n^2) 预处理 ---------- */
long long C[MAXN + 1][MAXN + 1];
void buildPascal(int n) {
    for (int i = 0; i <= n; ++i) {
        C[i][0] = C[i][i] = 1;
        for (int j = 1; j < i; ++j)
            C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD;
    }
}

/* ---------- ② 阶乘 + 逆元：O(n) 预处理，O(1) 查询 ---------- */
vector<long long> fact, invFact;
long long qpow(long long a, long long e) {
    long long r = 1; a %= MOD;
    while (e) { if (e & 1) r = r * a % MOD; a = a * a % MOD; e >>= 1; }
    return r;
}
void buildFact(int n) {
    fact.assign(n + 1, 1);
    invFact.assign(n + 1, 1);
    for (int i = 1; i <= n; ++i) fact[i] = fact[i - 1] * i % MOD;
    invFact[n] = qpow(fact[n], MOD - 2);                  // 费马小定理求 n! 的逆元
    for (int i = n; i >= 1; --i) invFact[i - 1] = invFact[i] * i % MOD;   // 倒推各级逆元
}
long long comb(int n, int m) {
    if (m < 0 || m > n) return 0;
    return fact[n] * invFact[m] % MOD * invFact[n - m] % MOD;
}

/* ---------- ③ 卢卡斯定理：C(n,m) mod p = C(n%p, m%p) * C(n/p, m/p) mod p ---------- */
long long lucas(long long n, long long m, long long p) {
    if (m == 0) return 1 % p;
    /* 小范围暴力算 C(n%p, m%p) */
    long long ni = n % p, mi = m % p;
    if (mi > ni) return 0;
    long long num = 1, den = 1;
    for (long long i = 1; i <= mi; ++i) {
        num = num * ((ni - i + 1) % p) % p;
        den = den * (i % p) % p;
    }
    long long small = num * qpow(den, p - 2) % p;         // p 是质数才能这样求逆元
    return small * lucas(n / p, m / p, p) % p;
}

/* ---------- 卡特兰数：Cat(n) = C(2n,n) / (n+1) ---------- */
long long catalan(int n) {
    return comb(2 * n, n) * qpow(n + 1, MOD - 2) % MOD;
}

int main() {
    buildPascal(20);
    cout << "杨辉三角 C(5,2) = " << C[5][2] << "\n";               // 10

    buildFact(100000);
    cout << "阶乘逆元 C(10,3) = " << comb(10, 3) << "\n";         // 120
    cout << "C(100, 50) mod 1e9+7 = " << comb(100, 50) << "\n";   // 538992043

    cout << "卡特兰数 Cat(0..6) = ";
    for (int i = 0; i <= 6; ++i) cout << catalan(i) << ' ';
    cout << "\n";     // 1 1 2 5 14 42 132

    /* 卢卡斯定理：大 n、小质数模数 */
    cout << "C(10^18, 10^9) mod 10007 = " << lucas(1000000000000000000LL, 1000000000LL, 10007) << "\n";
    return 0;
}

13.6.7 高精度运算：当 long long 也不够用时

long long 最大约 9.22 × 10¹⁸，只够存 19 位十进制数。 而 100! 有 158 位、2^1000 有 302 位——这类题就必须手写高精度。 基本思路很简单：用数组/vector 存每一位数字（低位在前，方便进位）， 然后手工模拟竖式运算。

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

/* ============================================================
   高精度整数：加法 / 减法 / 乘法（高精×高精） / 除法（高精÷高精）
   存储：vector<int>，低位在前（小端），base = 10
   ============================================================ */
typedef vector<int> Big;

Big fromString(const string& s) {
    Big a;
    for (int i = (int)s.size() - 1; i >= 0; --i) a.push_back(s[i] - '0');
    while (a.size() > 1 && a.back() == 0) a.pop_back();     // 去掉前导零
    return a;
}
string toString(const Big& a) {
    string s;
    for (int i = (int)a.size() - 1; i >= 0; --i) s += char('0' + a[i]);
    return s;
}

/* ---------- 加法 ---------- */
Big add(const Big& a, const Big& b) {
    Big c;
    int carry = 0;
    for (size_t i = 0; i < a.size() || i < b.size() || carry; ++i) {
        int t = carry;
        if (i < a.size()) t += a[i];
        if (i < b.size()) t += b[i];
        c.push_back(t % 10);
        carry = t / 10;
    }
    return c;
}

/* ---------- 比较：a > b 返回 1，相等 0，小于 -1 ---------- */
int cmp(const Big& a, const Big& b) {
    if (a.size() != b.size()) return a.size() > b.size() ? 1 : -1;
    for (int i = (int)a.size() - 1; i >= 0; --i)
        if (a[i] != b[i]) return a[i] > b[i] ? 1 : -1;
    return 0;
}

/* ---------- 减法：保证 a >= b ---------- */
Big sub(const Big& a, const Big& b) {
    Big c;
    int borrow = 0;
    for (size_t i = 0; i < a.size(); ++i) {
        int t = a[i] - borrow - (i < b.size() ? b[i] : 0);
        if (t < 0) { t += 10; borrow = 1; } else borrow = 0;
        c.push_back(t);
    }
    while (c.size() > 1 && c.back() == 0) c.pop_back();
    return c;
}

/* ---------- 乘法：高精 × 高精，O(n*m) ---------- */
Big mul(const Big& a, const Big& b) {
    if ((a.size() == 1 && a[0] == 0) || (b.size() == 1 && b[0] == 0)) return Big{0};
    Big c(a.size() + b.size(), 0);
    for (size_t i = 0; i < a.size(); ++i)
        for (size_t j = 0; j < b.size(); ++j)
            c[i + j] += a[i] * b[j];               // 先全部累加，最后统一进位
    for (size_t i = 0; i + 1 < c.size(); ++i) {
        c[i + 1] += c[i] / 10;
        c[i] %= 10;
    }
    while (c.size() > 1 && c.back() == 0) c.pop_back();
    return c;
}

/* ---------- 高精 × 低精度（常用优化，O(n)） ---------- */
Big mulSmall(const Big& a, int k) {
    Big c;
    long long carry = 0;
    for (size_t i = 0; i < a.size() || carry; ++i) {
        long long t = carry;
        if (i < a.size()) t += (long long)a[i] * k;
        c.push_back(t % 10);
        carry = t / 10;
    }
    while (c.size() > 1 && c.back() == 0) c.pop_back();
    return c;
}

/* ---------- 除法：高精 ÷ 高精，返回 {商, 余数} ----------
   思路：从高位到低位逐位"落位"，试商 0..9（也可二分），用减法确定。
   这里用 O(n*m) 的实现，n 为被除数位数。 */
pair<Big, Big> divide(const Big& a, const Big& b) {
    if (b.size() == 1 && b[0] == 0) { cout << "除数为 0！\n"; return {Big{0}, Big{0}}; }
    Big q, r;                                   // q: 商, r: 当前余数
    q.assign(a.size(), 0);
    for (int i = (int)a.size() - 1; i >= 0; --i) {
        r.insert(r.begin(), a[i]);              // 把 a[i] 落到余数最低位（相当于 r = r*10 + a[i]）
        while (r.size() > 1 && r.back() == 0) r.pop_back();
        int cnt = 0;
        while (cmp(r, b) >= 0) {                // 反复减，直到不够减
            r = sub(r, b);
            ++cnt;
            if (cnt > 9) break;                 // 安全保护
        }
        q[i] = cnt;                             // 第 i 位的商
    }
    while (q.size() > 1 && q.back() == 0) q.pop_back();
    return {q, r};
}

int main() {
    Big a = fromString("98765432109876543210");
    Big b = fromString("12345678901234567890");

    cout << "a = " << toString(a) << "\n";
    cout << "b = " << toString(b) << "\n";
    cout << "a + b = " << toString(add(a, b)) << "\n";        // 111111111011111111100
    cout << "a - b = " << toString(sub(a, b)) << "\n";        // 86419753208641975320
    cout << "a * b = " << toString(mul(a, b)) << "\n";

    /* ---------- 经典应用：求 n! （高精度） ---------- */
    Big fact = fromString("1");
    for (int i = 1; i <= 50; ++i) fact = mulSmall(fact, i);
    cout << "50! = " << toString(fact) << "\n";            // 65 位
    cout << "50! 的位数 = " << fact.size() << "\n";         // 65

    /* ---------- 高精度除法 ---------- */
    Big x = fromString("100000000000000000000");
    Big y = fromString("7");
    auto res = divide(x, y);
    cout << "10^20 / 7 = " << toString(res.first)
         << " ... " << toString(res.second) << "\n";
    return 0;
}

13.6.8 博弈论入门：Nim 游戏与 SG 函数

Nim 游戏：有 n 堆石子，第 i 堆有 a[i] 个。两人轮流操作， 每次可以从任意一堆中取走任意多个（至少一个），取走最后一个石子的人获胜。 问先手是否有必胜策略。

为什么？两个关键事实：

• 终局 Nim 和为 0：所有堆都空时 0 ⊕ 0 ⊕ … ⊕ 0 = 0。
• 和为 0 的局面，任何操作都会让它变成非 0：从某堆取走石子必然改变这一堆的值， 异或和随之改变（不可能保持 0）。
• 和为非 0 的局面，一定存在一种操作把它变成 0：设异或和为 s ≠ 0， 取 s 的最高位，必然存在某堆 a[i] 在该位为 1； 令 a[i] ← a[i] ⊕ s（这个值一定小于 a[i]，所以是合法操作）， 此时新的异或和变成 s ⊕ a[i] ⊕ (a[i] ⊕ s) = 0。

于是「非 0 局面」总能走到「0 局面」，而「0 局面」只能走到「非 0 局面」—— 先手从非 0 出发，每轮都把 0 局面丢给对手，最终对手面对「全空」的 0 局面而输。

SG 函数（Sprague-Grundy）把这个结论推广到任意公平组合游戏（ICG）： 对每个状态 x 定义

结论：整个游戏是若干子游戏的「异或和」，先手必胜当且仅当各子游戏 SG 值的异或和 ≠ 0。 对单堆取石子游戏（可取 1..k 个），可以验证 SG(x) = x mod (k+1)； Nim 是 k = ∞ 的特例，此时 SG(x) = x，异或和就是 Nim 和。

#include <iostream>
#include <vector>
#include <set>
#include <cstring>
using namespace std;

/* ============================================================
   博弈论：Nim 游戏 + SG 函数（Sprague-Grundy 定理）
   ============================================================ */

/* ---------- Nim：异或和判断 ---------- */
bool nimWin(const vector<int>& a) {
    int x = 0;
    for (int v : a) x ^= v;
    return x != 0;                 // 非 0 → 先手必胜
}

/* 返回一个必胜的第一步（把异或和变成 0）：返回 {堆下标, 取后剩余} */
pair<int,int> nimFirstMove(const vector<int>& a) {
    int x = 0;
    for (int v : a) x ^= v;
    if (x == 0) return {-1, -1};                 // 必败局面，无必胜走法
    for (int i = 0; i < (int)a.size(); ++i) {
        int target = a[i] ^ x;                   // 这一堆应该剩下多少
        if (target < a[i]) return {i, target};    // 合法（必须真的取走石子）
    }
    return {-1, -1};
}

/* ---------- SG 函数：mex ---------- */
int mex(const set<int>& s) {
    int g = 0;
    while (s.count(g)) ++g;
    return g;
}

/* 单堆取石子：每次可取 1..k 个，求 SG 值表（n 个石子的局面） */
vector<int> sgTable(int n, const vector<int>& moves) {
    vector<int> sg(n + 1, 0);
    for (int i = 1; i <= n; ++i) {
        set<int> reach;
        for (int m : moves)
            if (m <= i) reach.insert(sg[i - m]);
        sg[i] = mex(reach);
    }
    return sg;
}

int main() {
    /* ---------- Nim 游戏 ---------- */
    vector<int> a = {3, 4, 5};
    cout << "Nim {3,4,5}：异或和 = " << (3 ^ 4 ^ 5) << "，" << (nimWin(a) ? "先手必胜" : "先手必败") << "\n";
    auto mv = nimFirstMove(a);
    cout << "必胜第一步：把第 " << mv.first + 1 << " 堆（" << a[mv.first] << " 个）取到剩 " << mv.second << " 个\n";
    /* 3^4^5 = 2 ≠ 0 → 先手必胜。把第 1 堆 3 变成 3^2 = 1，剩下 {1,4,5}，异或和 1^4^5 = 0 ✓ */

    vector<int> b = {1, 2, 3};
    cout << "Nim {1,2,3}：异或和 = " << (1 ^ 2 ^ 3) << "，" << (nimWin(b) ? "先手必胜" : "先手必败") << "\n";
    /* 1^2^3 = 0 → 先手必败 */

    /* ---------- SG 函数：每次可取 1、3、4 个石子 ---------- */
    vector<int> moves = {1, 3, 4};
    vector<int> sg = sgTable(12, moves);
    cout << "取 1/3/4 个石子的 SG 值（0..12）：";
    for (int i = 0; i <= 12; ++i) cout << sg[i] << ' ';
    cout << "\n";
    /* 输出：0 1 0 1 2 3 2 0 1 0 1 2 3（周期为 7，这是常见的 SG 周期现象） */
    cout << "n = 10 时 SG = " << sg[10] << (sg[10] ? "（必胜）" : "（必败）") << "\n";

    /* ---------- 多堆游戏的组合：异或各堆 SG 值 ---------- */
    vector<int> piles = {5, 7, 9};
    int x = 0;
    for (int p : piles) x ^= sg[p];
    cout << "三堆 {5,7,9} 的 SG 异或和 = " << x << "，" << (x ? "先手必胜" : "先手必败") << "\n";
    return 0;
}

13.6.9 二分与三分：最容易被边界条件坑死的两个算法

二分的思想简单到一句话：「每次砍掉一半」。 但二分的代码是公认的易错点——l <= r 还是 l < r？ mid + 1 还是 mid？return l 还是 return r？ 这一节给出两套可以直接背的模板。

（1）整数二分：两套模板

把二分问题统一成「在单调序列中找满足某个条件的第一个位置」或「最后一个位置」：

/* 区间 [l, r] 为候选答案，循环结束时 l == r
   条件 check(mid) = (a[mid] >= x)
   返回：第一个满足条件的位置；若全不满足，返回 r+1 */
int lowerBound(const vector<int>& a, int x) {
    int l = 0, r = (int)a.size();          // 注意 r 取 n（哨兵位）
    while (l < r) {
        int mid = l + (r - l) / 2;         // 下取整
        if (a[mid] >= x) r = mid;          // mid 可能是答案 → r = mid
        else l = mid + 1;                  // mid 不可能是答案 → l = mid + 1
    }
    return l;                              // l == r 就是答案
}

/* 返回：最后一个满足条件的位置；若全不满足，返回 l-1 */
int lastLe(const vector<int>& a, int x) {
    int l = 0, r = (int)a.size() - 1;
    while (l < r) {
        int mid = l + (r - l + 1) / 2;     // ★ 上取整，防止死循环
        if (a[mid] <= x) l = mid;          // mid 可能是答案 → l = mid
        else r = mid - 1;                  // mid 不可能是答案 → r = mid - 1
    }
    return a.empty() ? -1 : (a[l] <= x ? l : -1);
}

（2）实数二分与三分

实数二分：不判断相等，而是迭代固定次数（通常 100 次，足够把区间缩小到 2⁻¹⁰⁰）， 或者判断 r − l < eps。推荐固定次数——eps 选大了精度不够，选小了可能死循环。

三分法：用于求单峰 / 单谷函数的极值。把区间分成三份， 比较两个三等分点 m1 < m2 的函数值： 求最大值时，若 f(m1) < f(m2) 则极值在 [m1, r]（砍掉左边），否则在 [l, m2]。

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;

/* ============================================================
   二分与三分模板合集
   ============================================================ */

/* ---------- ① 整数二分：第一个 >= x 的位置（0 基，找不到返回 n） ---------- */
int lowerBound(const vector<int>& a, int x) {
    int l = 0, r = (int)a.size();
    while (l < r) {
        int mid = l + (r - l) / 2;
        if (a[mid] >= x) r = mid; else l = mid + 1;
    }
    return l;
}

/* ---------- ② 整数二分：最后一个 <= x 的位置（找不到返回 -1） ---------- */
int lastLe(const vector<int>& a, int x) {
    int l = 0, r = (int)a.size() - 1;
    while (l < r) {
        int mid = l + (r - l + 1) / 2;            // 上取整
        if (a[mid] <= x) l = mid; else r = mid - 1;
    }
    return (l < (int)a.size() && a[l] <= x) ? l : -1;
}

/* ---------- ③ 二分答案：求最小的可行值（check 单调：false...false true...true） ---------- */
bool check(long long x) {
    return x * x >= 50;                           // 例：求最小的 x 使 x^2 >= 50
}
long long minFeasible(long long lo, long long hi) {
    while (lo < hi) {
        long long mid = lo + (hi - lo) / 2;
        if (check(mid)) hi = mid; else lo = mid + 1;
    }
    return lo;
}

/* ---------- ④ 实数二分：固定迭代 100 次，最稳 ---------- */
double f(double x) { return x * x * x - 2 * x - 5; }    // 求零点
double realBinarySearch(double l, double r) {
    for (int it = 0; it < 100; ++it) {
        double mid = (l + r) / 2;
        if (f(mid) > 0) r = mid; else l = mid;
    }
    return l;
}

/* ---------- ⑤ 三分法：求单峰函数最大值 ---------- */
double g(double x) { return -(x - 3) * (x - 3) + 10; }   // 峰值在 x = 3，最大 10
double ternaryMax(double l, double r) {
    for (int it = 0; it < 100; ++it) {
        double m1 = l + (r - l) / 3;
        double m2 = r - (r - l) / 3;
        if (g(m1) < g(m2)) l = m1;              // 峰在右边 → 砍掉左边
        else r = m2;                            // 峰在左边 → 砍掉右边
    }
    return l;                                   // 返回极值点
}

int main() {
    vector<int> a = {1, 3, 3, 5, 7, 9, 11};
    cout << "第一个 >= 6 的位置 = " << lowerBound(a, 6) << "\n";      // 4（a[4] = 7）
    cout << "第一个 >= 12 的位置 = " << lowerBound(a, 12) << "\n";    // 7（= n，不存在）
    cout << "最后一个 <= 6 的位置 = " << lastLe(a, 6) << "\n";       // 3（a[3] = 5）
    cout << "第一个 >= 5 的位置 = " << lowerBound(a, 5) << "\n";     // 3

    cout << "最小的 x 使 x^2 >= 50：" << minFeasible(1, 100) << "\n";  // 8（7²=49 < 50，8²=64）

    cout << "x³-2x-5 的零点 ≈ " << realBinarySearch(2, 3) << "\n";    // 约 2.0945514815
    double xm = ternaryMax(-10, 10);
    cout << "三分法求峰值点 x ≈ " << xm << "，最大值 = " << g(xm) << "\n";   // 3，10
    return 0;
}

13.6.10 数学类算法速查表

13.7 六大范式综合对比表

这张表是本章的「总纲」，考前一定要能默画出来。它把六大范式的核心思想、适用条件、 复杂度特征、经典问题和正确性保证放在一起对照。

13.7.1 三大关系的等价改写（考试最爱考）

13.7.2 复杂度速查：看到数据范围就该想到算法

13.8 工程视角：这六把锤子在真实系统里敲什么

前面七节把六种范式从定义到代码过了一遍，但它们看起来还像「考试用的东西」。 这一节回答一个更实际的问题：输入法、git、测序仪、编译器后端， 到底在哪些地方用到了这些范式？答案可能出乎意料——用得最多、最不声不响的那个， 正是 13.5 节花了一整节讲的动态规划。

工程代码里几乎不会出现「教科书式的纯范式」，真实系统多是 「一个范式做骨架、另一个做加速、再加工程近似」的混合体。下面每处落点都按同一个三段式讲： 用什么范式 → 为什么非它不可 → 代价是什么。

13.8.1 动态规划在工程里的三个「顶梁柱」

（1）序列比对：生物信息学的双子星

序列比对是生物信息学最重要的算法：「两条 DNA 序列有多像」决定了基因注释、进化分析、 病毒溯源的全部下游结论。两个奠基性算法都是二维 DP： Needleman–Wunsch（1970）做全局比对（状态 F[i][j] = 「a 前 i 个字符与 b 前 j 个字符的最优比对得分」，三种来源同样是上、左、左上， 再加打分矩阵与空位罚分）；Smith–Waterman（1981）做局部比对，只找最像的那一段。

把它们和 13.5.3 的 LCS 并排看：状态定义、下标含义、三种来源、初始化形状完全一致， 区别只在合并操作——LCS 用 max 且相等时 +1，比对用带权 max 加打分与罚分。 LCS 就是「不算分、等权」的全局比对；局部比对只在每项末尾加一个下限 0 （H[i][j] = max(0, 三种来源)，答案取全表最大值），含义是「分数已为负， 不如从这格重新开始」——一格改动，就从「比全长」变成「比局部」。

代价有三层：① 全表是 O(nm) 时间与空间； ② 想要对齐路径就不能只留一行——只求分数可滚动数组压到 O(min(n,m))， 要还原「怎么排」必须存下每格来源方向（Hirschberg 用分治压回 O(m)，时间翻倍）； ③ 规模根本不允许：人类基因组约 3.2×10⁹ 个碱基，全表 DP 是 10¹⁸ 量级。 所以工业工具走启发式剪枝：BLAST 先找短的完全相同片段（种子）， 只对种子周围的窄带做精细 DP；今天的 BWA、minimap2 是同一思路。 范式没变，变的是「只算值得算的那一小块」。

（2）编辑距离、Viterbi 与输入法

编辑距离（Levenshtein distance）是图 13-17 与 edit_distance.cpp 的主角： 它与 LCS 共用同一张表，只是把「奖励匹配」换成三种操作的代价、把 max 换成 min， 第 0 行/列也从全 0 变成 0,1,2,3…。它支撑着四件事：拼写纠错（与词典逐词比距离取最近）、 输入法（拼音与候选词匹配、按错隔壁键的容错）、模糊搜索与实体消歧、 以及生物信息学。

真正的工程难点不是这个 DP，而是「和谁比」：词典十万条，单次比较 O(nm)， 暴力就是 O(N·nm)。所以工程上分两段——先在检索层把候选砍到几十个 （n-gram 倒排索引、BK 树、Levenshtein 自动机），再对候选跑精确 DP。 这与 第 10 讲「先建索引再查找」一致： 算法负责正确性，数据结构负责把搜索空间砍小。

Viterbi 算法是同一套思想在概率模型上的化身：语音识别、词性标注、通信解调都建立在 隐马尔可夫模型上，解码就是求「让观测出现概率最大的隐状态路径」—— dp[t][s] = 「到时刻 t 停在状态 s 的最大累计概率」，取上一时刻所有状态的最大值， 再回溯恢复路径。唯一实质性的工程改动是把概率连乘改成对数相加： 上百帧概率连乘会下溢到 0—— 这是统计类 DP 的第一条纪律：能用对数就别用连乘。

（3）文本 diff：git diff 背后的 LCS

git diff 与所有差异显示工具，底层都是「求两序列的最小编辑脚本」， 而「保留不动的部分」正是两文件的最长公共子序列——编辑脚本越短 ⇔ 公共部分越长， 所以 diff 与 13.5.3 的 LCS 是同一个问题的两种说法。 这里有个值得记住的事实：最小编辑脚本一般不唯一，diff 的输出也就不唯一。 因为 A[i] != B[j] 时要往上走或往左走，两条路可能给出完全相同的长度， 选哪条只是「把差异算在哪一块」的分歧。以 kitten → sitting 为例： 距离是 3，但「k 替换为 s」与「删 k 再插 s」是同样步数的两种合法方案， 显示成补丁就是「改一个字符」还是「删一行加一行」—— 只要差异行数相同，它们就都是「最小」的。

代价：教科书版 LCS 是 O(nm) 时间与空间，两个几十万行的文件就是 10¹⁰ 量级。 所以 git 默认用 Myers 的 O(ND) 差分算法（1986）：它不填满整张表， 而是从编辑距离 D 出发做「带预算的广度搜索」，相似文件（D 很小）时快得惊人。

把下面这段代码和图 13-17 逐行对上。它就是上面几个落点共享的内核： 「用什么打分、和谁比、比完怎么用」各不同，DP 部分一字不改。

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

/* ============================================================
   编辑距离（Levenshtein Distance）—— 二维 DP 的标准写法
   状态：dp[i][j] = 把 a 的前 i 个字符改成 b 的前 j 个字符所需的最少操作数
   转移：dp[i][j] = min( dp[i-1][j]   + 1,     // 上：删除 a 的第 i 个字符
                         dp[i][j-1]   + 1,     // 左：插入 b 的第 j 个字符
                         dp[i-1][j-1] + (a[i-1] != b[j-1]) )  // 左上：替换或匹配
   边界：dp[i][0] = i（删光 a 的前 i 个字符）；dp[0][j] = j（从空串插满 b 的前 j 个字符）

   与 13.5 节 LCS 的异同：
   相同——状态语义都是「前缀 vs 前缀」，都从上、左、左上三格推出，边界都在第 0 行/列，
         遍历顺序都是 i、j 双重正序循环，答案都在右下角 dp[n][m]。
   不同——LCS 求最长公共部分，越匹配越长，用 max，只在字符相等时走左上并 +1；
         编辑距离求最少改动次数，越匹配越短，用 min，三路都要走（删除 / 插入也计入代价）。
         另一处外观差异在边界：LCS 第 0 行/列全是 0，编辑距离是 0,1,2,3…。
   ============================================================ */
int editDistance(const string& a, const string& b) {
    int n = (int)a.size(), m = (int)b.size();
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
    for (int i = 0; i <= n; ++i) dp[i][0] = i;   // 第一列：删掉 a 的前 i 个字符
    for (int j = 0; j <= m; ++j) dp[0][j] = j;   // 第一行：插入出 b 的前 j 个字符
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j) {
            int sub = (a[i - 1] == b[j - 1]) ? 0 : 1;   // 相同就不用替换
            dp[i][j] = min(min(dp[i - 1][j] + 1,        // 上：删除
                               dp[i][j - 1] + 1),       // 左：插入
                           dp[i - 1][j - 1] + sub);     // 左上：替换 / 匹配
        }
    return dp[n][m];
}

/* 空间优化：二维 O(nm) 压成一维 O(min(n, m))。
   滚动时「左上角」的值会被覆盖，必须先用 diag 存下来；
   dp[0] 每一行都要更新为 i，否则第 0 列会一直停在 0。 */
int editDistance1D(const string& a, const string& b) {
    int n = (int)a.size(), m = (int)b.size();
    if (m > n) return editDistance1D(b, a);      // 让 m 取较小值，空间 O(min(n,m))
    vector<int> dp(m + 1, 0);
    for (int j = 0; j <= m; ++j) dp[j] = j;      // 第 0 行
    for (int i = 1; i <= n; ++i) {
        int diag = dp[0];                        // dp[i-1][j-1]，先存旧值再覆盖
        dp[0] = i;                               // 第 i 行的第 0 列：删光
        for (int j = 1; j <= m; ++j) {
            int old = dp[j];                     // 覆盖前存下 dp[i-1][j]
            int sub = (a[i - 1] == b[j - 1]) ? 0 : 1;
            dp[j] = min(min(dp[j] + 1, dp[j - 1] + 1), diag + sub);
            diag = old;                          // 下一格的「左上」就是这一格上方的旧值
        }
    }
    return dp[m];
}

/* 打印整张 dp 表，对照图 13-17 逐格检查 */
void printTable(const string& a, const string& b) {
    int n = (int)a.size(), m = (int)b.size();
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
    for (int i = 0; i <= n; ++i) dp[i][0] = i;
    for (int j = 0; j <= m; ++j) dp[0][j] = j;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j) {
            int sub = (a[i - 1] == b[j - 1]) ? 0 : 1;
            dp[i][j] = min(min(dp[i - 1][j] + 1, dp[i][j - 1] + 1), dp[i - 1][j - 1] + sub);
        }
    cout << "      ";
    for (int j = 0; j <= m; ++j) cout << (j == 0 ? '-' : b[j - 1]) << ' ';
    cout << "\n";
    for (int i = 0; i <= n; ++i) {
        cout << (i == 0 ? '-' : a[i - 1]) << "  :  ";
        for (int j = 0; j <= m; ++j) cout << dp[i][j] << ' ';
        cout << "\n";
    }
}

int main() {
    string a = "kitten", b = "sitting";
    cout << "把 " << a << " 改成 " << b << " 最少需要 "
         << editDistance(a, b) << " 步\n";                       // 3
    cout << "一维滚动数组结果 = " << editDistance1D(a, b) << "\n"; // 3（对照用）

    cout << "----- DP 表（行 = " << a << "，列 = " << b << "）-----\n";
    printTable(a, b);            // 最后一格 dp[6][7] = 3，与图 13-17 完全一致

    /* 边界情况必须单独测：空串最容易把下标和初始化坑死 */
    cout << "\nkitten -> kitten : " << editDistance("kitten", "kitten") << "\n"; // 0
    cout << "abc    -> abcde  : " << editDistance("abc", "abcde") << "\n";       // 2
    cout << "(空)   -> abc    : " << editDistance("", "abc") << "\n";             // 3
    cout << "abc    -> (空)   : " << editDistance("abc", "") << "\n";             // 3

    cout << "\n时间 O(n*m)；空间二维 O(n*m)，可优化成一维 O(min(n,m))，\n";
    cout << "但一维版只能给出距离，要还原「怎么改的」必须保留整张表。\n";
    return 0;
}

13.8.2 贪心：从路由器到操作系统的「每步拍板」

13.4 节说过「贪心必须证明」。规律很明显：贪心被大规模使用的地方， 往往是「问题结构足够规整」或「有理论下界兜底」的地方。

（1）网络：Dijkstra 是最短路的贪心

路由器算路（OSPF）、导航算最快路线，底层都是单源最短路， 而 Dijkstra 本质上就是一个贪心（第 09 讲）：每次从「还没确定的顶点」里 挑出当前距离最小的那个，宣布它的最短路已确定，再用它松弛邻居。 贪心选择性质成立靠的是边权非负——当前最近的未确定点不可能再被更长的路径绕近。 代价正在这里：一旦出现负权边，贪心立刻失效，必须换成 Bellman–Ford 那一类 允许反复修正的算法。另一层代价是选最小值的开销：朴素写法 O(V²) 只在稠密图划算， 真实路网用二叉堆做到 O((V+E) log V)；理论上更快的斐波那契堆因常数巨大而几乎不用—— 理论复杂度更优不等于工程更快。

（2）编码与压缩：Huffman 是最优前缀码的贪心

Huffman 编码（第 07 讲）是贪心最纯粹的胜利：反复合并频率最小的两个结点， 得到的编码可证明是所有前缀码里平均码长最短的（交换论证）， 它出现在 gzip / zip（DEFLATE）、JPEG、MP3、HTTP/2 头部压缩里。 代价有两条：① 必须两遍——先统计全局频率表再编码，频率表还要传给解码方； ② 最优性带着约束——它假设每个符号占整数比特，而信息论下界是实数： 概率 0.9 的符号理论最优码长约 0.152 比特，Huffman 只能给 1 比特，浪费近 7 倍， 所以更贴近下界的是算术编码 / 区间编码。 贪心给出的是「这个模型下」的最优，不是「信息论意义下」的最优。

（3）调度：SPT 规则

操作系统任务队列、打印队列、订单履约排程里有一条老规矩：最短处理时间优先（SPT）—— 每次先做预计耗时最短的任务。在「单机、任务同时到达、最小化平均等待时间」这个模型下， 它可以严格证明最优（交换论证：两个相邻任务中长的在前，交换不会让平均等待时间变差）。 代价是饥饿：只要短任务源源不断，长任务就永远排不上。 而且它的证明依赖「处理时间事先已知」，现实中工时是估计值，估错就全盘退化。 所以真实系统用多级反馈队列（新任务进高优先级，用完时间片没做完就降级） 加上老化（aging）——把等久的任务优先级慢慢抬高，用工程手段补上 SPT 缺的那块。

（4）存储：Belady 最优页面置换是「不可实现的下界」

这是本节最值得记住的工程思想。Belady 最优算法（OPT）的规则是 淘汰「未来最久才会被再次访问」的那页：它是贪心， 而且可证明是所有页面置换算法里缺页最少的。 代价只有一条，但这条代价致命——它需要预知未来的访问序列， 而程序下一步要访问哪个地址，任何操作系统都不可能提前知道。 所以它的工程地位很特殊：它不是一个能跑的算法，而是一个理论下界。 工程上用 LRU（最近最少使用）近似它——把「未来最久不用」偷换成「过去最久没用」， 赌程序的访问局部性。这个赌在多数真实程序上有效，但有明确的失效场景： 顺序扫描大数组时，LRU 会把马上还要用的页提前淘汰；加上硬件实现成本（每次访问都要维护 链表位置，太贵），所以真实系统用的是 CLOCK、二次机会、ARC 这些改良版。 「最优不可实现 → 用可实现的近似 → 近似在特定场景失效 → 再造更好的近似」， 这条链是系统工程最真实的写照，而它的起点是一个贪心算法的理论最优性。

（5）找零：贪心的正确性必须证明，不能凭直觉

人民币面额为什么可以贪心？因为相邻面额之间有倍数关系（1、2、5、10、20、50、100）， 这种面额系统称为「规范（canonical）」系统，可以证明贪心恰好最优。 但只要面额不是这套规整结构，贪心立刻出错：以 {1, 3, 4} 为例， 凑 6 时贪心先取最大的 4，剩下 2 只能用 1+1，共 3 枚；而最优解是 3+3，只要 2 枚。 贪心给出 3，正确答案是 2，错得很安静——它不崩溃也不报错，只是答案偏大； 这时必须换 DP：dp[x] = min over c of (dp[x − c] + 1)。

工程含义有三点：① 判断一个硬币系统是否规范可以多项式时间完成， 但任意给定面额集合的找零问题本身是 NP-hard 的，所以自动售货机、积分兑换 往往不追求最优，只追求「够快、够合理」； ② 面额是业务配置项，改一个面额就可能让贪心从正确变错误， 所以任何用贪心的地方都要有测试用例保护，不能靠「上次是对的」； ③ 贪心失败一定能用 DP 救回来（13.4.7 讲过「贪心 = 只保留一个状态的 DP」）， 代价是复杂度从 O(面额数) 变成 O(目标金额 × 面额数)—— 这就是「局部最优」换「全局最优」要付的钱。

13.8.3 分治：大规模系统的默认骨架

（1）MapReduce / 大数据：分治的产业化形态

Hadoop、Spark、Flink 这一整代大数据框架的核心模型 MapReduce 就是分治的工程化形态： 把输入切成若干分片（划分）→ 每个分片独立跑 map（递归求解）→ 按 key 洗牌 → 每个 key 独立跑 reduce（合并）。 第 11 讲的归并排序就是这套流程的最小可运行样例： 切分数组、两半各自排序、合并两个有序序列—— 一个能讲清的归并排序，已经包含了 MapReduce 的全部思想要素。 为什么必须是分治而不是 DP？因为 13.3.2 的四条件里最关键的是「子问题相互独立」： map 任务互不通信，才能线性扩展到几千台机器；而 DP 的子问题有重叠依赖， 天然难以直接并行，这也是大数据流水线里几乎看不到 DP 的原因。 代价是三条：shuffle 是瓶颈（中间结果要按键重分发、排序、落盘、走网络，开销常超过计算本身）、 数据倾斜（某个 key 数据量远超其他，拖慢整个 reduce 阶段）、 以及「合并操作必须满足结合律」——只有可结合的操作才能安全地任意分组重排。

（2）FFT：分治在信号与数值计算里的王者

朴素计算 n 点 DFT 需要 O(n²) 次复数乘法，而快速傅里叶变换（FFT） 利用 e^(−2πi/n) 的对称性与周期性，把 n 点 DFT 拆成两个 n/2 点的 DFT 再合并，得到 T(n) = 2T(n/2) + O(n)，由主定理（13.3.7）情形二得 O(n log n)。 这个递推式和归并排序一模一样——你不是在学两个算法，而是在看同一个分治骨架的两次应用。 它的覆盖面极广：Wi-Fi / 4G / 5G 的 OFDM 调制解调、MP3 / AAC 音频编码、 JPEG 图像压缩（8×8 分块 DCT，与 DFT 同源）、MRI / CT 重建，以及最容易被忽略的 大整数乘法：把大数看作多项式系数，用 FFT 做系数卷积 （「多项式乘法 = 系数卷积」，可由「FFT → 逐点相乘 → 逆 FFT」在 O(n log n) 完成）。 整数乘法的演进 O(n²) → Karatsuba O(n^1.585)（也是分治）→ Toom–Cook → FFT， 正是「分治一路把指数往下压」的历史。

（3）快速选择与快速幂：把分治用在「一半」上

13.6.5 的快速幂就是分治用在幂运算上的结果：把 a^n 拆成 「先算 a^(n/2) 再平方」，T(n) = T(n/2) + O(1)， 由主定理得 O(log n)。它在密码学里不可替代：RSA 的核心是模幂 a^b mod m， 现代密钥 2048 位以上，指数 b 本身就有 2000 多位——朴素连乘要约 2²⁰⁴⁸ 次乘法， 一个永远算不完的数；快速幂只要约 2048 次。 这一个算法的存在与否直接决定了 RSA 能不能用。 同族的快速选择（Quickselect）更妙：求「第 k 小」时用快排的划分把数组分成两半后， 只递归进入包含第 k 小元素的那一半——与快速排序只差一行， 却把 O(n log n) 变成期望 O(n)，平均意义上打破了比较排序下界； 工程上用于找中位数、算分位数（P99 延迟）、找 top-k。 代价是对划分轴敏感，最坏 O(n²)，所以生产实现用随机取轴或 BFPRT； 而数据能装进内存时，维护一个大小为 k 的堆（O(n log k)）往往更好写、还支持流式—— 又一次，工程最优不等于渐进复杂度最优。

13.8.4 回溯：NP 难世界的工业底座

（1）SAT 求解器与约束满足：回溯长成了工业级巨兽

「布尔可满足性问题」（SAT）问的是：给一个布尔公式，是否存在一组变量取值使它为真。 它是历史上第一个被证明的 NP 完全问题，理论上「难」；但工程上， 现代 SAT 求解器能稳定处理几十万变量、几百万子句的工业实例。 骨架就是 13.2 节的回溯——选变量赋值 → 递归 → 冲突就回退——再叠加几项决定性改进： 单元传播（子句只剩一个未赋值变量时它被迫取值，可立刻传播，把大量分支在生成前砍掉）、 冲突驱动子句学习（CDCL）（分析冲突成因，学出新子句加回公式，保证同样的冲突不再发生）、 非时序回溯（一次跳回真正相关的决策层，而不是只退一层）、 重启与子句删除（定期丢掉搜索进度重新开始，避免在坏分支里耗尽时间）。 它的下游极其庞大：数独、排课、芯片布线与版图验证、软硬件的形式化验证、物流排程； SMT 求解器进一步结合整数算术、数组与位向量理论，成为程序分析与符号执行的引擎。 代价是：最坏情况仍是指数时间，只能靠启发式与工程优化绕开； 而且「建模」本身成了核心竞争力——同一个问题换一种编码，求解时间可能差几个数量级， 工程师的价值从「写搜索算法」转移到了「把问题翻译成约束」。 CSP 里的通用剪枝启发式（MRV 优先选取值最少的变量、度启发式、最少约束值） 配合约束传播（弧相容 AC-3）与前向检查，正是 13.2.3「约束函数」的系统化版本。

（2）正则表达式引擎：回溯的甜蜜与灾难

这是回溯最贴近每个程序员的一个落点。主流正则引擎（PCRE、Python 的 re、Java、 早期 JavaScript）都用回溯式匹配：遇到 a* 先贪心吃下尽可能多的字符， 为满足后续模式再一个字符一个字符地退回来——正是一次标准的回溯搜索。 反向引用、环视这些「非正则」特性只有靠回溯才能实现，所以这些引擎宁愿忍受指数复杂度。

但代价就是那个「最坏指数级」。当量词嵌套且整体匹配失败时， 引擎会把所有可能的切分方式全试一遍，这就是灾难性回溯（catastrophic backtracking）： 用 (a+)+$ 去匹配 30 个 a 后面跟一个 b 的字符串， 末尾的 $ 永远不成立，但引擎会在「如何把 a 串切成若干段」的全部组合上穷举—— 约 2²⁹ 种切法，程序直接卡死。这样的正则写进服务端，攻击者只要发一个精心构造的短字符串 就能打满 CPU，这就是 ReDoS（正则表达式拒绝服务），现实中引发过多个公开 CVE， 是「算法复杂度直接变成安全漏洞」的教科书案例。 防御有三条：① 换引擎——用把正则编译成 NFA / DFA 的线性时间引擎 （RE2、Rust 的 regex、Go 的 regexp），匹配时间与模式复杂度无关， 代价是放弃反向引用与部分环视；② 改模式——用占有量词 a++、 原子组 (?>…) 禁止引擎回头重试；③ 限制输入——限制被匹配串长度与超时。 把「回溯的重试次数」当作可控资源来管理，而不是相信它总会很快返回。

（3）编译器、硬件验证与物流：求解器是工业底座

编译器后端最经典的优化之一是寄存器分配：把成百上千个临时变量映射到物理寄存器。 它的标准建模是图着色——变量是顶点，活跃区间重叠就连边，颜色就是寄存器编号， 问题变成「用 k 种颜色给图上色」（正是 13.2.7 的回溯案例）。 图着色是 NP 完全的，所以教科书讲回溯；工业编译器实际做的是「图着色 + 溢出 （把放不下的变量塞回内存）+ 把最难的实例交给 ILP / SAT 求解器」。 硬件验证、物流排程（车辆路径、装箱、人员排班）、芯片布局布线走的都是同一条路： 把问题编码成 SAT / ILP / SMT，交给工业求解器——理由很实际， 现代求解器集成了几十年的剪枝、学习、重启技术，手写启发式几乎追不上。 代价有三条：① 编码开销（一个自然的约束可能要用成百上千个子句表达）； ② 可解释性差（求解器只还你一个赋值，不解释为什么这样排最好，调试困难）； ③ 超时后只能降级——通常只返回「当前最好可行解 + 与下界的差距（gap）」， 你必须接受「不保证最优」。

把这些落点和 13.2.9 的结论对上：回溯的价值不在于它快， 而在于它能在指数级解空间里给出精确答案，并且可以随手加剪枝。 一旦规模超出「剪枝后能算完」的范围，工程上只有三条出路—— 换更强的剪枝与学习（CDCL）、换问题表述（换编码或换求解器）、 或接受近似解（启发式 + 下界，容忍 gap）。

13.8.5 四范式工程对照表

下面这张表是本节的总纲，建议和 13.7 的「课堂版对比表」对照着看： 13.7 关心「考试怎么答」，这张表关心「工程怎么选」。

13.9 本章小结、易错点与自测

13.9.1 必须记住的十二件事

13.9.2 易错点总清单

13.9.3 自测题（6 道，答案折叠）

for (int i = 1; i <= n; ++i)
    for (int j = V; j >= w[i]; --j)          // 倒序！
        dp[j] = max(dp[j], dp[j - w[i]] + v[i]);

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

/* 混合背包：01 + 完全 + 多重（二进制拆分） */
int main() {
    int n = 4, V = 10;
    int w[5] = {0, 2, 3, 4, 5};
    int v[5] = {0, 3, 4, 5, 6};
    int s[5] = {0, 1, 0, 3, 2};          // 1=只能用一次, 0=无限, 其他=有限个

    vector<int> dp(V + 1, 0);
    for (int i = 1; i <= n; ++i) {
        if (s[i] == 0) {                 // 完全背包：正序
            for (int j = w[i]; j <= V; ++j)
                dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
        } else if (s[i] == 1) {          // 01 背包：倒序
            for (int j = V; j >= w[i]; --j)
                dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
        } else {                         // 多重背包：二进制拆分 + 01 倒序
            int cnt = s[i];
            for (int k = 1; cnt > 0; k <<= 1) {
                int take = min(k, cnt);
                cnt -= take;
                int nw = take * w[i], nv = take * v[i];
                for (int j = V; j >= nw; --j)
                    dp[j] = max(dp[j], dp[j - nw] + nv);
            }
        }
    }
    cout << "混合背包最优价值 = " << dp[V] << "\n";
    return 0;
}

13.9.4 配套编程练习