第十二章动态规划入门

第七章用递推计算台阶走法，第十章用搜索展开选择。本章把两件事接起来：搜索时有些问题被反复计算；如果到达同一个问题后，未来的选择只由当前状态决定，就可以把答案存下并复用。动态规划（DP）的状态、转移和计算顺序，都是为这件事服务的。

先从台阶、连续子段、活动安排、网格和背包建立方法，再回头比较递推与记忆化搜索。掌握这些之后，还会学习恢复方案、滚动数组、子序列、计数背包、区间 DP，最后完成一道把排序与背包计数接在一起的综合题。后半章仍给出完整推导，第一次阅读可在每节的小表格处停下来自己算一遍。

阅读前需要掌握数组、递推、递归与搜索。区间 DP 会用到第四章的前缀和；多边形计数会用到取余，其必要规则在使用处说明，第十三章再系统讲解。下文各段代码都是独立的 C++17 完整程序，分别说明输入和输出；同名数组不能直接拼接。容量按每节给出的范围分配，全局数组初始为零。

从重复搜索建立动态规划

1. 从台阶计数看见重复子问题

有 $n$ 级台阶，每次走 $1$ 级或 $2$ 级，求恰好到达第 $n$ 级的走法数。比如到第 $4$ 级的走法为 $1+1+1+1$ 、 $1+1+2$ 、 $1+2+1$ 、 $2+1+1$ 、 $2+2$ ，共 $5$ 种。

先从终点倒着提问：“走到第 $4$ 级的最后一步是什么？”若最后走 $1$ 级，要先走到第 $3$ 级；若最后走 $2$ 级，要先走到第 $2$ 级。继续展开求第 $3$ 级时，又会询问第 $2$ 级。同一个“到达第 $2$ 级有多少走法”被算了两遍，级数更大时会重复得更多。

台阶计数的重复调用：求第 4 级的两个分支都需要第 2 级

图中两个蓝色的“到第 $2$ 级”是同一个问题。选择路径虽然不同，但只要目标级数同为 $2$ ，其走法数就一样；这里才可以共享答案。换成按到达位置统计：令 $f_i$ 为到达第 $i$ 级的走法数。最后一步只能从第 $i-1$ 级走 $1$ 级，或从第 $i-2$ 级走 $2$ 级；两类走法互不重叠且覆盖全部情况，因此

f_i=f_{i-1}+f_{i-2}\quad(i\ge2).

到达第 $0$ 级且一步不走，是一种空走法，所以 $f_0=1$ ；到达第 $1$ 级只有一种走法，所以 $f_1=1$ 。手算时先写两个已知位置，再从左向右填：

级数 $i$	$0$	$1$	$2$	$3$	$4$
从 $i-1$ 走来	—	—	$1$	$2$	$3$
从 $i-2$ 走来	—	—	$1$	$1$	$2$
$f_i$	$1$	$1$	$2$	$3$	$5$

例如 $f_4=3+2=5$ 。每个新值只依赖较小下标，按下标递增计算即可。这里的 $f_0=1$ 表示“不走”这一种空走法，而不是已有一条实际台阶。

#include <bits/stdc++.h>
using namespace std;
long long f[100];
int n;
int main()
{
    scanf("%d", &n);
    f[0] = f[1] = 1;
    for (int i = 2; i <= n; i++)
    {
        f[i] = f[i - 1] + f[i - 2];
    }
    printf("%lld\n", f[n]);
}

程序输入一个整数 $n$ ，输出走法数。本节限定 $0\le n\le91$ ； $n=91$ 时答案为 $7540113804746346429$ ，仍能由 long long 保存， $n=92$ 就会超出。每个状态只计算一次，时间与空间均为 $O(n)$ ；若只需最终答案，可保留相邻两项，把额外空间降为 $O(1)$ 。扩大 $n$ 时还要重新检查计数范围。

这个例子展示了设计 DP 时应回答的五个问题： $f_i$ 表示什么，答案从哪些互不重叠的情况转移，最小状态是什么，按什么顺序计算，以及最后取哪个状态。若第 $i$ 级破损，则该级的走法数应为 $0$ ；转移关系必须服从状态含义，而不是机械套用公式。

2. 状态需要保留未来会用到的信息

台阶只需记位置。但换一道题，位置可能不足以判断下一步能否接上已有方案。先看两个例子：连续子段须知道前一段在哪里结束；活动计划须知道昨天选了什么。看完这两个例子，再总结怎样定义足够使用的状态。

2.1 最大连续子段和：必须以当前位置结尾

给定整数序列，选择一个连续且非空的子段，使元素和最大。枚举左右端点并重新求和会重复累加同一段元素。先试着保存“前 $i$ 项中的最大子段和”。在 $[5,-100,4]$ 的前两项里，这个值是 $5$ ，由第 $1$ 项形成；但要把第 $3$ 项接到某个连续子段后面，能接的只能是以第 $2$ 项结尾的子段。把 $5+4$ 当作新连续子段会越过中间的 $-100$ 。因此仅有历史最优值不够，需要知道能被当前项接上的最优值。

令 $f_i$ 表示必须以第 $i$ 项结尾的最大子段和。以 $i$ 结尾的最优子段，或者只有 $a_i$ ，或者把一个以 $i-1$ 结尾的最优子段接上 $a_i$ ：

f_1=a_1,\qquad f_i=\max(a_i,f_{i-1}+a_i)\quad(i\ge2).

以序列 $[-2,3,-1,2,-5]$ 手算，两个值的区别如下：

位置 $i$	$1$	$2$	$3$	$4$	$5$
必须以 $i$ 结尾的 $f_i$	$-2$	$3$	$2$	$4$	$-1$
前 $i$ 项的最大值	$-2$	$3$	$3$	$4$	$4$

最后一项的 $f_5=-1$ ，但全局最优仍是中间子段 $[3,-1,2]$ 的和 $4$ 。因此最终答案是所有 $f_i$ 的最大值。代码只需保存前一个 $f_i$ 和全局最优值：

#include <bits/stdc++.h>
using namespace std;
const int N = 200000 + 10;
int n;
long long a[N], f, ans;
int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        scanf("%lld", &a[i]);
    }
    f = ans = a[0];
    for (int i = 1; i < n; i++)
    {
        f = max(a[i], f + a[i]);
        ans = max(ans, f);
    }
    printf("%lld\n", ans);
}

程序输入 $n$ 和 $n$ 个整数，输出最大非空子段和。约定 $1\le n\le2\times10^5$ 、 $|a_i|\le10^9$ ，任意子段和的绝对值至多 $2\times10^{14}$ ，使用 long long。首项初始化使全负数时仍选取一个真实元素，不会把和为 $0$ 的空子段当成答案。每项处理一次，时间 $O(n)$ ；除保存输入的 $O(n)$ 数组外，状态只占 $O(1)$ 额外空间。若边读边更新，可连输入数组也省去。整数类型应能容纳题目允许的子段和。

2.2 三活动计划：结尾类型也是状态

连续 $n$ 天，每天从三项活动中选一项并取得当天收益，不能连续两天选同一项，求最大总收益。若只存前一天的最高收益，就不知道它以哪项活动结尾。只看前一天，活动 $0,1,2$ 的收益为 $(10,9,0)$ ：最高值 $10$ 来自活动 $0$ 。今天若必须选活动 $0$ ，昨天只能取 $9$ ，不能取 $10$ 。另一组收益 $(9,10,0)$ 也有最高值 $10$ ，但今天选活动 $0$ 时反而可以接这个 $10$ 。相同的“昨日最高 $10$ ”无法回答今天同一个问题，必须把昨日结尾类型存进状态。

令 $f_{i,j}$ 表示前 $i$ 天的最高收益，且第 $i$ 天选活动 $j$ ，其中 $j\in\{0,1,2\}$ 。若今天选 $j$ ，昨天只能选另外两项。设第 $i$ 天选 $j$ 的收益为 $w_{i,j}$ ，则

f_{i,j}=w_{i,j}+\max_{k\ne j}f_{i-1,k}.

第一天没有前一天，直接令 $f_{1,j}=w_{1,j}$ 。例如三天收益依次为 $(10,40,70)$ 、 $(20,50,80)$ 、 $(30,60,90)$ ：

天数	以活动 $0$ 结尾	以活动 $1$ 结尾	以活动 $2$ 结尾
第 $1$ 天	$10$	$40$	$70$
第 $2$ 天	$90$	$120$	$120$
第 $3$ 天	$150$	$180$	$210$

例如第 $2$ 天以活动 $0$ 结尾的值为 $20+\max(40,70)=90$ 。最后答案为第 $n$ 天三个结尾状态中的最大值。由于当天只读取昨天的三个值，用两个长度为 $3$ 的数组交替保存即可。

三活动按昨日结尾分类：今天选活动 0 只能连接昨日活动 1 或 2

图中每个昨日格子保存一个结尾类型的最高收益。今天选择活动 $0$ 时，图中的两条箭头只来自昨日活动 $1,2$ ；同样方法分别计算今天活动 $1,2$ 。这说明“已处理天数”和“结尾类型”合在一起才足以继续决策。状态相同，应表示后续可作的选择相同；不影响后续的完整历史则不必保存。容量 DP 还需区分“恰好用 $j$ ”与“至多用 $j$ ”，它们的初值将有所不同。

#include <bits/stdc++.h>
using namespace std;
int n;
long long f[3], g[3], w[3];
int main()
{
    scanf("%d", &n);
    for (int j = 0; j < 3; j++)
    {
        scanf("%lld", &f[j]);
    }
    for (int i = 2; i <= n; i++)
    {
        for (int j = 0; j < 3; j++)
        {
            scanf("%lld", &w[j]);
        }
        g[0] = w[0] + max(f[1], f[2]);
        g[1] = w[1] + max(f[0], f[2]);
        g[2] = w[2] + max(f[0], f[1]);
        for (int j = 0; j < 3; j++)
        {
            f[j] = g[j];
        }
    }
    printf("%lld\n", max({f[0], f[1], f[2]}));
}

程序输入天数 $n$ ，随后每行给出当天三项收益，输出最大总收益。这里 $1\le n\le2\times10^5$ 、单项收益绝对值不超过 $10^9$ ，故使用 long long。每个状态恰好从两种合法的前一天结尾转移，时间为 $O(n)$ 、额外空间为 $O(1)$ 。同一天的三个新状态都从旧数组 $f$ 读取，写入 $g$ 后再整体复制回 $f$ ，避免把当天刚更新的收益当成昨天的收益。

3. 网格 DP：按最后一步合并路径

考虑从 $(0,0)$ 出发，每步只向右或向下，求到 $(n,m)$ 的路径数。若某些格子禁止进入，经过它们的路径不计入答案。直接枚举移动序列会反复计算到同一格子的后续路线。

令 $f_{i,j}$ 为从起点到 $(i,j)$ 的合法路径数。到达一个非起点格子的最后一步只可能来自上方或左方，两类路径的最后一步不同，所以可以相加。禁止格的 $f_{i,j}=0$ ；起点有一条长度为零的路径， $f_{0,0}=1$ 。

没有禁止格时，走到 $(2,2)$ 的小表格为：

$i\backslash j$	$0$	$1$	$2$
$0$	$1$	$1$	$1$
$1$	$1$	$2$	$3$
$2$	$1$	$3$	$6$

若中心 $(1,1)$ 禁止进入，重新从起点逐格填表，而不是只改中心一个数字：

$i\backslash j$	$0$	$1$	$2$
$0$	$1$	$1$	$1$
$1$	$1$	$0$ （禁止）	$1$
$2$	$1$	$1$	$2$

网格路径数逐格传播：中心禁止格归零，其后续格从上方与左方重新相加

动画的黄色格是当前要计算的位置，蓝色格是已处理或待处理的普通格，红色中心格表示禁止进入。静态两张表分别给出无障碍与有障碍的最终数值；即使不播放动画，也能用 $f_{1,2}=f_{0,2}+f_{1,1}=1+0$ 、 $f_{2,2}=f_{1,2}+f_{2,1}=2$ 核对传播过程。第一行和第一列只有一侧来源，棋盘外不能算成一条路径。处理 $(i,j)$ 前，它的上方和左方已经算好。

第十章迷宫路径计数允许四向移动，且每条路径不能重复经过格子；两条路径即使到达同一坐标，已经走过的格子也可能不同，因此不能只按坐标合并。这里始终只向右或向下，已经走过的格子位于当前位置的上方或左方，不会改变后面格子的可走性，坐标才足以描述后续问题。

《过河卒》题面在此基础上，把马所在格及马一步可跳到的八个格子标为禁止。下面程序输入终点坐标 $n,m$ 与马的坐标 $x,y$ 。先标记棋盘内的禁止格，再按行列递增计算，最后输出路径数。原题保证起点不受控制； $n,m\le20$ 时，无障碍路径数至多为 $\binom{40}{20}=137846528820$ ，需要使用 long long。

#include <bits/stdc++.h>
using namespace std;
const int N = 25;
int n, m, x, y;
long long f[N][N];
bool vis[N][N];
int dx[9] = {0, -2, -2, -1, -1, 1, 1, 2, 2};
int dy[9] = {0, -1, 1, -2, 2, -2, 2, -1, 1};
int main()
{
    scanf("%d%d%d%d", &n, &m, &x, &y);
    for (int k = 0; k < 9; k++)
    {
        int u = x + dx[k], v = y + dy[k];
        if (u >= 0 && u <= n && v >= 0 && v <= m)
        {
            vis[u][v] = true;
        }
    }
    if (!vis[0][0])
    {
        f[0][0] = 1;
    }
    for (int i = 0; i <= n; i++)
    {
        for (int j = 0; j <= m; j++)
        {
            if (vis[i][j] || (i == 0 && j == 0))
            {
                continue;
            }
            if (i > 0)
            {
                f[i][j] += f[i - 1][j];
            }
            if (j > 0)
            {
                f[i][j] += f[i][j - 1];
            }
        }
    }
    printf("%lld\n", f[n][m]);
}

每个合法格的来源都来自更小的行号或列号，因此依赖没有环；每格只处理一次，时间与空间为 $O((n+1)(m+1))$ 。如果允许向上或向左返回，依赖可能成环，这种单次扫描就失去依据。若把目标改为最大路径权值，合并方式应从加法变为取最大值，并为不可达格设置明确标记；棋盘外的默认 $0$ 不能凭空提供路径。

4. 0/1 背包：先写二维状态，再压缩空间

有若干件物品，每件最多选一次，第 $i$ 件消耗时间 $t_i$ 、获得价值 $w_i$ ，总时间不超过 $T$ ，求最大价值。《采药》题面的输入先给总时间 $T$ 和草药数 $m$ ；题面范围为 $T\le1000$ 、 $m\le100$ ，单件耗时和价值均为 $1$ 至 $100$ 。本节也沿用这两个字母。

枚举每件“选或不选”会产生 $2^m$ 个方案。处理到第 $i$ 件时，后续只需知道已处理到哪里、还允许使用多少时间；具体选过哪些草药无需重复保存。令 $F_{i,j}$ 表示只考虑前 $i$ 件、总耗时不超过 $j$ 的最大价值。

第 $i$ 件要么不选，答案来自 $F_{i-1,j}$ ；要么选，前面物品只剩 $j-t_i$ 的容量，答案来自 $F_{i-1,j-t_i}+w_i$ 。于是

F_{i,j}= \begin{cases} F_{i-1,j},&j<t_i,\\ \max\bigl(F_{i-1,j},F_{i-1,j-t_i}+w_i\bigr),&j\ge t_i. \end{cases}

例如第二件耗时 $3$ 、价值 $4$ ，算 $F_{2,5}$ 时，“不选”从上一行 $F_{1,5}=3$ 来；“选”从上一行剩余容量 $2$ 的 $F_{1,2}=3$ 来，得到 $3+4=7$ 。本例剩余容量 $2$ 放不下耗时 $3$ 的第二件，所以两种来源的数值恰好一样；这不代表可以普遍读取本行。例如容量改为 $6$ ，本行 $F_{2,3}$ 可能已经选择第二件，再加一次就会把它重复选入。下文用一件物品的表格具体展示这个问题。

两种来源都在第 $i-1$ 层，因为当前物品最多用一次。令 $F_{0,j}=0$ ：不选任何物品，对任意容量上限都合法。以 $T=5$ 、两件物品 $(t,w)=(2,3),(3,4)$ 手算：

已处理物品	$j=0$	$1$	$2$	$3$	$4$	$5$
无	$0$	$0$	$0$	$0$	$0$	$0$
第一件后	$0$	$0$	$3$	$3$	$3$	$3$
第二件后	$0$	$0$	$3$	$4$	$4$	$7$

最后 $F_{2,5}=7$ 来自两件都选。程序输入 $T,m$ ，随后 $m$ 行各给出 $t_i,w_i$ ，输出最大价值。先把二维转移写成代码，能直接核对每次都读取上一层：

#include <bits/stdc++.h>
using namespace std;
const int N = 110, V = 1010;
int T, m, t[N], w[N], f[N][V];
int main()
{
    scanf("%d%d", &T, &m);
    for (int i = 1; i <= m; i++)
    {
        scanf("%d%d", &t[i], &w[i]);
    }
    for (int i = 1; i <= m; i++)
    {
        for (int j = 0; j <= T; j++)
        {
            f[i][j] = f[i - 1][j];
            if (j >= t[i])
            {
                f[i][j] = max(f[i][j], f[i - 1][j - t[i]] + w[i]);
            }
        }
    }
    printf("%d\n", f[m][T]);
}

二维数组需要 $O(mT)$ 时间和空间；代码的两维容量分别按 $m\le100$ 、 $T\le1000$ 选取。由于第 $i$ 层只读第 $i-1$ 层，可以让一维数组 $f_j$ 在每轮开始时代表旧层，结束时代表新层。关键不是机械记“倒序”，而是判断读取时的 $f_{j-t_i}$ 还属于哪一层。

只放一件耗时 $2$ 、价值 $3$ 的物品，容量为 $0$ 至 $4$ 。每个容量的旧层都是 $0$ 。若从小到大更新，先使 $f_2=3$ ，再算 $f_4$ 时读取的 $f_2$ 已经是本轮的新值，错误得到 $6$ ；这等于把同一件物品用两次。倒着算时先处理 $f_4$ ，读取的 $f_2$ 仍是旧层的 $0$ ，所以 $f_4$ 只得到 $3$ 。

扫描方式	初始 $f_0$ 至 $f_4$	第一次关键更新	第二次关键更新	本轮最终值
错误正序	$0,0,0,0,0$	$f_2=3$ （新层）	$f_4=f_2+3=6$ （读到新层）	$0,0,3,3,6$
正确倒序	$0,0,0,0,0$	先算 $f_4=0+3=3$ （读旧 $f_2$ ）	再算 $f_2=3$	$0,0,3,3,3$

同一件物品的 0/1 背包倒序和完全背包正序更新：容量 4 读取的是旧 f2 还是新 f2

动画前三帧演示 0/1 背包倒序，后三帧演示允许重复使用时的正序；黄色为当前目标容量，蓝色为同轮已经写入的值。容量 $4$ 都要读取容量 $2$ ，但前者读旧层的 $0$ ，后者读本轮新值 $3$ 。上表固定了动画的关键数值。另一个容易忽略的容量 $3$ 也只能放这件物品一次，所得最大价值为 $3$ 。

#include <bits/stdc++.h>
using namespace std;
const int V = 1010;
int T, m, f[V];
int main()
{
    scanf("%d%d", &T, &m);
    for (int i = 1; i <= m; i++)
    {
        int t, w;
        scanf("%d%d", &t, &w);
        for (int j = T; j >= t; j--)
        {
            f[j] = max(f[j], f[j - t] + w);
        }
    }
    printf("%d\n", f[T]);
}

一维程序的输入输出和范围与二维版本相同。倒序保证本轮读取的较小容量还属于旧层，因此一维代码与二维转移等价。时间仍为 $O(mT)$ ，额外空间降为 $O(T)$ 。本节的初值与答案位置依赖“耗时不超过 $T$ 、价值非负、允许一件也不选”；要求恰好用完时间时，初始化必须改变。

5. 完全背包：本轮结果可以继续使用

若每种物品可选任意多件，选入第 $i$ 种后还可以再选它。二维状态仍表示处理前 $i$ 种、容量不超过 $j$ 的最优价值，但“选一次当前物品”的来源变成当前层 $F_{i,j-t_i}+w_i$ ，因为这个来源可能已经选过同种物品。

仍看耗时 $2$ 、价值 $3$ 的物品，容量为 $4$ 。一维数组从小到大更新：先得到容量 $2$ 的价值 $3$ ，再用这个本轮新值算出容量 $4$ 的价值 $6$ ，正好表示选两件。若仍倒序，就只能选一次。

这次正序读到新层的 $f_2=3$ 正是需要的：容量 $4$ 的 $6$ 表示同一种物品选两次。二维看， $F_{i,j}$ 的“再选一件”来源是本层 $F_{i,j-t_i}$ ；从小到大才能先把来源算好。同一张动画因此解释两种循环方向，差别来自题目的选择次数，而不是两个需要背下来的模板。

《疯狂的采药》题面给出总时间 $t$ 、物品种类数 $m$ 。程序输入总时间 $T$ 、种类数 $m$ ，随后每行给出正整数耗时与价值。题目中 $T\le10^7$ 、 $mT\le10^7$ ，单件耗时与价值均不超过 $10^4$ 。每种可选任意多件，也允许不选；总收益至多 $10^{11}$ ，使用 long long 保存。

#include <bits/stdc++.h>
using namespace std;
const int V = 10000000 + 10;
int T, m;
long long f[V];
int main()
{
    scanf("%d%d", &T, &m);
    for (int i = 1; i <= m; i++)
    {
        int t, w;
        scanf("%d%d", &t, &w);
        for (int j = t; j <= T; j++)
        {
            f[j] = max(f[j], f[j - t] + w);
        }
    }
    printf("%lld\n", f[T]);
}

时间为 $O(mT)$ ，有效状态空间为 $O(T)$ ；程序按上界分配的数组约占 $80$ MB。该题给出的 $mT\le10^7$ 约束使时间可以据此估算，容量达到 $10^7$ 时仍需为数组预留相应内存。若允许耗时为 $0$ 且价值为正，某种物品可以无限选择，最优值无界，不能直接套用普通完全背包循环。

0/1 背包的倒序与完全背包的正序，根源在于“当前物品能否使用本轮刚算出的状态”。先写清二维来源属于旧层还是本层，再决定压缩后的循环方向。

6. 记忆化搜索：按需求计算同一批状态

第一节的台阶计数也可以写成递归：求第 $i$ 级，就分别求第 $i-1$ 、第 $i-2$ 级。若不保存结果，计算第 $i-2$ 级的过程会在不同分支中反复出现。增加数组后，非边界状态只在第一次请求时递归计算，以后直接取保存的值； $f_0,f_1$ 则可立即返回。这就是记忆化搜索。

台阶依赖图：递归第一次求 f2 时存入缓存，另一条分支再次请求 f2 时直接命中

图中实线沿依赖向下，虚线回到已算好的 $f_2$ 。自底向上递推按 $0,1,2,3,4$ 的顺序填表；记忆化从 $4$ 开始，沿递归请求找到较小状态，返回时写入缓存，再遇到 $2$ 时直接读取。两者使用同一个状态和转移，只是计算时机不同。

下面再次解决台阶计数，但这次只展示计算顺序的变化。数组 $f$ 中的 $f_i=-1$ 表示尚未计算；走法数始终非负，所以这个标记不会与合法答案混淆。若状态的合法答案可能为 $0$ ，用 $0$ 当“未计算”会让这类状态反复求值，应另设 vis 或使用不会与答案冲突的标记。

#include <bits/stdc++.h>
using namespace std;
int n;
long long f[100];
long long dfs(int u)
{
    if (u <= 1)
    {
        return 1;
    }
    if (f[u] != -1)
    {
        return f[u];
    }
    return f[u] = dfs(u - 1) + dfs(u - 2);
}
int main()
{
    scanf("%d", &n);
    fill(f, f + 100, -1);
    printf("%lld\n", dfs(n));
}

输入输出和第 1 节相同，仍限定 $0\le n\le91$ 。对这个例子，记忆化与从小到大的递推都只计算 $O(n)$ 个状态，总时间、空间均为 $O(n)$ ；记忆化还占用深度可达 $n$ 的调用栈。它的优势是按请求展开依赖，状态很多但只访问少数状态时可能减少计算。缓存并不能解决依赖环，使用前仍要证明每次递归都走向更小或有其他无环顺序。

上面的例子已分别回答“记录什么”和“按什么顺序算”。接下来的专题仍从这些问题出发，只是答案可能变成一组选择、一个可达判断或方案数；阅读时可先独立手算表格，再检查代码。

深入专题与综合应用

7. 恢复一组最优方案

已经会求最大连续子段和之后，若题目要求输出子段的位置，仅保存最优值就不够了。可以在每次转移时同时记住来源：若 $a_i$ 单独开始更好，新段左端点是 $i$ ；若接在旧段后更好，左端点保持不变。当全局最优值更新，再保存当时的左右端点。

对序列 $[-2,3,-1,2,-5]$ ，逐项追踪“以当前位置结尾”的和及其左端点：

位置（从 $1$ 起）	$1$	$2$	$3$	$4$	$5$
结尾和	$-2$	$3$	$2$	$4$	$-1$
当前段左端点	$1$	$2$	$2$	$2$	$2$
已存全局区间	$[1,1]$	$[2,2]$	$[2,2]$	$[2,4]$	$[2,4]$

最大连续子段和的来源与最优区间：从新起点或延长前段中选择

图中箭头表示“延长前一段”，没有箭头的第 $2$ 项表示重新开始。处理第 $4$ 项时保存的新最优为 $[2,4]$ ；第 $5$ 项使结尾和下降，但不改变已保存的全局区间。实际程序的数组下标从 $0$ 开始，故输出的这段是 [1,3]。输入范围和第 2.1 节相同；读入 $n$ 及序列，输出最优和、左端点、右端点。

#include <bits/stdc++.h>
using namespace std;
const int N = 200000 + 10;
int n, l, L, R;
long long a[N], f, ans;
int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        scanf("%lld", &a[i]);
    }
    f = ans = a[0];
    for (int i = 1; i < n; i++)
    {
        if (f < 0)
        {
            f = a[i];
            l = i;
        }
        else
        {
            f += a[i];
        }
        if (f > ans)
        {
            ans = f;
            L = l;
            R = i;
        }
    }
    printf("%lld %d %d\n", ans, L, R);
}

程序输出从 $0$ 开始编号的闭区间。l 保存当前结尾段的左端点，L,R 保存全局最优区间；全局初值为零，表示最初只选第一个元素。相等时延续当前段，也保留最先得到的全局最优段；若题目要求最短、最长或字典序最小的最优区间，需要改写并列时的比较。对背包等多维状态，恢复方案通常要保存物品层上的选择信息；一维数组不断覆写旧层，单独保存一个容量前驱不一定足够。

8. 滚动数组与更新方向

滚动数组解决的是保存空间的问题，求出的状态值不变。三活动计划已经使用两组长度为 $3$ 的数组： $f$ 保存昨天， $g$ 保存今天，整天计算完再替换。这是滚动数组。网格路径数还可以进一步压成一行，借此看清同一数组中“旧值”与“新值”如何同时存在。

处理到 $(i,j)$ 前， $f_j$ 保存上一行的 $f_{i-1,j}$ ；同一轮中左边的 $f_{j-1}$ 已更新为本行的 $f_{i,j-1}$ 。例如无障碍 $3\times3$ 小网格，在计算 $(1,1)$ 前，一维数组是 $[1,1,1]$ ；更新 $f_1$ 时，右侧旧 $f_1=1$ 来自上方，左侧新 $f_0=1$ 来自本行，得到 $2$ 。因此从左向右执行 $f_j\gets f_j+f_{j-1}$ 。禁止格要直接清零，不可让上一行路径穿过它；若 $(1,1)$ 禁止，更新到它时数组为 $[1,0,1]$ ，随后 $(1,2)$ 才从左边的 $0$ 和上方的 $1$ 得到 $1$ 。

#include <bits/stdc++.h>
using namespace std;
const int N = 25;
int n, m;
bool vis[N][N];
long long f[N];
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i <= n; i++)
    {
        for (int j = 0; j <= m; j++)
        {
            int x;
            scanf("%d", &x);
            vis[i][j] = x;
        }
    }
    f[0] = vis[0][0] ? 0 : 1;
    for (int i = 0; i <= n; i++)
    {
        for (int j = 0; j <= m; j++)
        {
            if (vis[i][j])
            {
                f[j] = 0;
            }
            else if (j > 0)
            {
                f[j] += f[j - 1];
            }
        }
    }
    printf("%lld\n", f[m]);
}

程序输入 $n,m$ ，再输入 $(n+1)\times(m+1)$ 个 $0/1$ 标记； $1$ 表示禁止进入。此处自设 $0\le n,m\le20$ ，输出路径数，容量与第三节一致。从上到下、每行从左到右扫描， $f_j$ 的旧值就是上方来源， $f_{j-1}$ 的新值就是左方来源。第一行与第一列只存在一侧来源；起点单独初始化。时间仍为 $O((n+1)(m+1))$ ，除输入禁止格外只用 $O(m+1)$ 额外空间。空间压缩前，应先列出每次更新读取哪个旧层状态、哪个新层状态，避免覆盖尚未使用的信息。

9. 最长上升子序列与合唱队形

子序列保持原有相对顺序，但允许跳过中间元素；连续子段则不允许跳过。例如 $[2,9,3,4]$ 中， $[2,3,4]$ 是上升子序列，却不是连续子段，因为跳过了 $9$ 。第 2 节的“以当前位置结尾”只能接相邻的前一项；这里要检查所有更早的位置。

给定身高序列，令 $up_i$ 表示必须以第 $i$ 位结尾的最长严格上升子序列长度。它可以只取当前人，也可以接在更早且更矮的人之后：

up_i=1+\max_{j<i,\,a_j<a_i}up_j,

以 $[2,9,3,4]$ 为例，来到末尾的 $4$ ，可接的更矮前驱是第 $1$ 项的 $2$ 和第 $3$ 项的 $3$ ；它们对应长度分别为 $1$ 与 $2$ ，所以选第 $3$ 项，得到长度 $3$ 。第 $2$ 项的 $9$ 对应长度 $2$ ，但不能接上 $4$ 。

上升子序列的前驱候选：末尾 4 可以接 2 或 3，不能接 9

图中的两条箭头是合法前驱，红色格中的 $9\not<4$ ，不能接到末尾 $4$ ；状态 $up_i$ 保存的是必须以 $i$ 结尾的长度，最后的答案才取所有结尾的最大值。若没有满足条件的 $j$ ，最大部分按 $0$ 处理。处理 $i$ 前，所有较小下标的状态都已计算，因此可直接枚举 $j$ 。

《合唱队形》要求删除最少的人，使剩余身高先严格上升再严格下降。固定峰顶 $i$ ，左侧使用 $up_i$ ；右侧令 $down_i$ 为从 $i$ 出发向右严格下降的最长长度，从右向左用同样的“小于”关系计算。峰顶被两边各计算一次，故保留人数为 $up_i+down_i-1$ 。

以 $[150,160,170,165,155]$ 为例， $up=[1,2,3,3,2]$ ， $down=[1,2,3,2,1]$ ；在身高 $170$ 的位置可保留 $3+3-1=5$ 人，因此无需删除。

#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int n, a[N], f[N], g[N], ans;
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
        f[i] = g[i] = 1;
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j < i; j++)
        {
            if (a[j] < a[i])
            {
                f[i] = max(f[i], f[j] + 1);
            }
        }
    }
    for (int i = n; i >= 1; i--)
    {
        for (int j = i + 1; j <= n; j++)
        {
            if (a[j] < a[i])
            {
                g[i] = max(g[i], g[j] + 1);
            }
        }
    }
    for (int i = 1; i <= n; i++)
    {
        ans = max(ans, f[i] + g[i] - 1);
    }
    printf("%d\n", n - ans);
}

程序输入 $n$ 及 $n$ 个身高，输出最少删除人数；f,g 分别对应 $up,down$ 。每个位置在两个方向各比较 $O(n)$ 次，时间为 $O(n^2)$ 、空间为 $O(n)$ ；题目给出的 $n\le100$ 足以使用这个版本。更大规模的单侧严格 LIS 可以维护“每种长度能达到的最小结尾”，并用二分在 $O(n\log n)$ 时间更新；这一数组记录的是各长度的最佳结尾，不保证各项同时来自同一条真实子序列，方案恢复还需另存来源。

10. 状态值、恰好容量与背包变式

背包的状态维度可以相同，保存的值却可能不同。先用一件耗时 $2$ 的物品看容量 $3$ ：“不超过 $3$ ”可以选这件，恰好用 $3$ 则没有方案。再看空物品集：恰好用 $0$ 有一份空方案；恰好用 $1,2,3$ 都不可达。

每处理一件物品，按“本件不选”或“本件选”分类。最大收益取两类的最大值，可达性取逻辑或，方案数在两类互不重复时相加。因此初值和合并运算都要跟着问题改变。

问题	空方案对应的 $f_0$	其他恰好容量的初值	合并方式
恰好容量的最大价值	$0$	不可达	取最大值
恰好容量是否可达	真	假	逻辑或
恰好容量的方案数	$1$	$0$	相加

例如仅有一件耗时 $2$ 、价值 $5$ 的物品，容量上限为 $3$ 时，“不超过 $3$ ”的最优价值为 $5$ ；“恰好消耗 $3$ ”却没有方案。若把所有容量的最优值都初始化为 $0$ ，后一种问题就会把不可达状态误当成合法空方案。写程序时，恰好容量的最大价值可把不可达格标为一个足够小的值，但转移前必须先判断来源可达，避免把哨兵值当真实收益参与加法。下面以布尔可达数组避开哨兵：初始仅容量 $0$ 可达，处理单件耗时 $x$ 时倒序更新。

#include <bits/stdc++.h>
using namespace std;
const int V = 10000 + 10;
int n, M;
bool f[V];
int main()
{
    scanf("%d%d", &M, &n);
    f[0] = true;
    for (int i = 1; i <= n; i++)
    {
        int x;
        scanf("%d", &x);
        for (int j = M; j >= x; j--)
        {
            f[j] = f[j] || f[j - x];
        }
    }
    printf("%d\n", f[M]);
}

程序先输入目标 $M$ 和物品数 $n$ ，再输入 $n$ 个正耗时，输出 $0$ 或 $1$ 。本例约定 $0\le M\le10000$ 、 $0\le n\le100$ ，每件耗时为 $1$ 至 $10^9$ 的整数。耗时超过 $M$ 的物品不会进入更新循环。它只回答“恰好容量是否可达”，并不把价值混进状态；时间为 $O(nM)$ 、空间为 $O(M)$ 。

10.1 恰好消费：不同下标分别计数

以 $[1,1,2,3]$ 为例，前两份价格相同，但“只选第一份”和“只选第二份”是两种下标集合。《小 A 点菜》中有 $n$ 份不同菜品，每份至多点一次，求总价恰好为 $M$ 的方案数。即使价格相同，不同菜品也按下标区分。令 $c_j$ 为已处理菜品中，总价恰好为 $j$ 的方案数，初始 $c_0=1$ 、其余为 $0$ 。处理价格 $a_i$ 时从 $M$ 向 $a_i$ 倒序更新：

c_j\gets c_j+c_{j-a_i}.

仍需倒序，因为一份菜品只能点一次。对 $M=4$ 逐轮手算：

已处理价格	$c_0$	$c_1$	$c_2$	$c_3$	$c_4$
无	$1$	$0$	$0$	$0$	$0$
第一份 $1$	$1$	$1$	$0$	$0$	$0$
第二份 $1$	$1$	$2$	$1$	$0$	$0$
第三份 $2$	$1$	$2$	$2$	$2$	$1$
第四份 $3$	$1$	$2$	$2$	$3$	$3$

价格为 $[1,1,2,3]$ 、目标为 $4$ 时，合法下标集合有三种：两份价格为 $1$ 的菜配价格为 $2$ 的菜，或分别用一份价格为 $1$ 的菜配价格为 $3$ 的菜。下面的程序输入 $n,M$ ，再输入 $n$ 个正价格，输出方案数，按原题使用 $n\le100$ 、 $M\le10000$ 。程序直接对应上表，并针对《小 A 点菜》只保证最终答案不超过 $2^{31}-1$ 的条件，把超过该界的中间计数截为 $2^{31}$ 。由于计数只会相加，任何真正能贡献到最终答案的中间状态若超过此界，最终答案也必超过题面保证的范围；因此截断不会改变合法输入的最终答案。

#include <bits/stdc++.h>
using namespace std;
const int V = 10000 + 10;
const long long lim = 1LL << 31;
int n, M;
long long c[V];
int main()
{
    scanf("%d%d", &n, &M);
    c[0] = 1;
    for (int i = 1; i <= n; i++)
    {
        int x;
        scanf("%d", &x);
        for (int j = M; j >= x; j--)
        {
            c[j] = min(lim, c[j] + c[j - x]);
        }
    }
    printf("%lld\n", c[M]);
}

例如处理第二份价格 $1$ 时，c[2] 读取本轮尚未改动的旧 c[1]=1，得到一种同时选两份的方案；c[1] 稍后才变成 $2$ 。时间为 $O(nM)$ ，空间为 $O(M)$ 。

方案数的整数范围要按所有中间状态检查。即使题面保证最终 $c_M$ 不超过 int，较小容量上的中间计数仍可能很大。上述饱和计数依赖“最终答案有已知上界”和“转移只做非负加法”；若要得到所有容量的精确计数，须按范围改用更宽整数或高精度，允许取模时才能按题意取模。

10.2 常见选择关系

以下模型继续按“当前物品可以怎样选”推导。先看状态为何要增加维度或改成组，再写出同一个物品（或同一组）内部的合法选择。

约束	状态或分组变化	关键依据
同时消耗金钱和时间	$f_{j,k}$ 保存两个资源上限	0/1 物品压缩后两个容量都倒序
每组至多选一件	一组只有“不选”或“选组内某一件”	组内选项都从上一组的旧层转移
主件须与附件配套	先列出本组允许的组合	不合法的单独附件不进入转移
某件最多选若干次	枚举本件使用数量	转移与优化都须保留数量限制

两种资源同时受限时，状态必须同时记允许使用的金钱和时间上限。例如只有 $(2,1)$ 与 $(1,2)$ 两件物品，金钱和时间上限都是 $2$ ：各选一件会用掉 $(3,3)$ ，不合法。更一般地，消耗 $(3,1)$ 与 $(2,2)$ 的金钱、时间之和都是 $4$ ，但在两个上限均为 $2$ 时，前者超出金钱上限，后者合法。只记相加后的“总消耗”就丢失了这一差别。对于每件最多一次的物品，压缩后的两个容量均倒序，这保证读到的是上一件处理完的旧状态。二维容量为 $M,T$ 时，直接实现常需 $O(nMT)$ 时间、 $O(MT)$ 空间，维度乘积必须先估算。

分组背包中，一组的候选只能“不选”或“选其中一件”。例如组内有耗时 $2$ 、价值 $3$ 和耗时 $3$ 、价值 $4$ 两件，容量 $5$ ；本组不能同时获得价值 $7$ 。应从处理上一组后的整行状态出发，逐一比较这三个选项，不能让选本组第一件后的新值继续选第二件。主件与附件题也先列出合法组内组合，如“不选、只选主件、主件加附件”，单独附件不能进入候选。若附件很多，还须先评估列举组合的代价。

一件最多选 $q$ 次时，二维转移可枚举选 $0,1,\ldots,q$ 件，来源统一取上一种物品的旧层，且所选数量乘单件耗时不能超过容量。例如只有一种耗时 $2$ 、价值 $3$ 的物品，最多选两件，容量 $6$ 时合法选择只有 $0,1,2$ 件，对应价值 $0,3,6$ ；完全背包可选三件得到 $9$ ，在这里却不合法。一般转移取上一层 $F_{i-1,j-kt_i}+kw_i$ 中所有满足 $0\le k\le q$ 且 $kt_i\le j$ 的最大值，再与不选的情况一起比较。时间上界与 $q$ 有关；若求最优值，才可研究二进制拆分等优化。方案计数时不同拆分方式可能表示同一种原始选法，不能直接照搬。

无限使用面值 $1,2$ 凑出 $3$ ，若不区分加入顺序，方案为 $1+1+1$ 与 $1+2$ ；若区分顺序，还要把 $2+1$ 单独计入。外层先遍历面值、内层正序遍历总额时，每种组合只按固定面值次序生成一次；外层先遍历总额、内层按最后加入的面值分类时，则得到有序序列数。循环顺序也在决定“什么算同一种方案”。

11. 区间 DP：按最后一次合并划分

第十一章的合并果子允许任意两堆合并，可以每次取最小的两堆；若只允许合并相邻石堆，这个选择可能不合法。给定一排正重量石堆，每次合并相邻两堆并支付新堆重量，求合成一堆的最小总代价。

以 $[3,2,4]$ 为例，最后一次合并前只能剩相邻的两段： $(3,2)\mid(4)$ 或 $(3)\mid(2,4)$ 。第一种先付 $3+2=5$ ，最后付 $3+2+4=9$ ，总计 $14$ ；第二种先付 $2+4=6$ ，最后仍付 $9$ ，总计 $15$ 。于是思考长区间时，不用猜第一步，枚举最后一次把它分开的边更容易保证不漏。

相邻石堆合并的两个最后分割点，以及长度一到三的状态计算顺序

图中竖线是最后一次合并前的分界，竖线两边要先各自合成一堆，最后再支付整段重量。下方的长度顺序表说明短区间先于长区间：长度 $1$ 的费用为 $0$ ，长度 $2$ 的费用分别是 $5,6$ ，长度 $3$ 才比较 $14,15$ 。

观察最后一次合并：整个区间 $[l,r]$ 在此之前一定已经分成相邻的两堆 $[l,k]$ 与 $[k+1,r]$ 。左右两段各自的合并过程互不干涉，最后再支付整个区间重量。令 $f_{l,r}$ 为把第 $l$ 至第 $r$ 堆合成一堆的最小代价， $p_i$ 为前 $i$ 堆重量和，则

f_{l,l}=0,\qquad f_{l,r}=\min_{l\le k<r}\left(f_{l,k}+f_{k+1,r}+p_r-p_{l-1}\right).

上述例子对应分割点 $k=2$ 与 $k=1$ 两种情况。任意完整方案都有确定的最后分割点，枚举全部 $k$ 不会漏掉可能的最优方案；固定分割点后，左右两段独立，分别选最优也不会让总代价变大。

计算较长区间前，左右两段的短区间必须已得到答案，因此按区间长度从小到大计算。下面先按题目范围选择类型。《石子合并（弱化版）》题面给出 $n\le300$ 、单堆重量至多 $1000$ ，这个范围的总代价上界为 $300\times300\times1000=9\times10^7$ ，因此程序使用 int。程序输入 $n$ 和各堆重量，输出最小总代价；权值更大的变式须重新估算并改用更宽类型。

#include <bits/stdc++.h>
using namespace std;
const int N = 310;
int n, a[N], pre[N], f[N][N];
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
        pre[i] = pre[i - 1] + a[i];
    }
    for (int len = 2; len <= n; len++)
    {
        for (int l = 1; l + len - 1 <= n; l++)
        {
            int r = l + len - 1;
            f[l][r] = INT_MAX;
            for (int k = l; k < r; k++)
            {
                f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + pre[r] - pre[l - 1]);
            }
        }
    }
    printf("%d\n", f[1][n]);
}

输入要求至少一堆；只有一堆时输出初始的 $0$ 。区间有 $O(n^2)$ 个，每个区间尝试 $O(n)$ 个断点，时间为 $O(n^3)$ 、空间为 $O(n^2)$ 。前缀和让每次读取整段重量只用 $O(1)$ 时间。

12. 综合例题：排序后固定最大值，再做背包计数

《CSP-J 2025·多边形》题面要求从 $n$ 根正长度木棍中选择一个下标集合，使选中数量至少为 $3$ ，且总长严格大于最长木棍的两倍。不同下标集合算不同方案，答案对 $998244353$ 取模。数据范围为 $n\le5000$ 、木棍长度不超过 $5000$ 。

条件同时涉及最大值与总和。先按长度升序排序；对每个选中集合，取其中排序位置最后的一根作为当前木棍。即使有相同长度，按位置区分后，每个集合仍有唯一的最后位置。设当前长度为 $a_i$ ，此前选中木棍的总长为 $S$ ，合法条件变为 $S>a_i$ 。

此前每根木棍都不长于 $a_i$ 且长度为正。若此前只选一根，其长度至多为 $a_i$ ，达不到 $S>a_i$ ；所以合法时此前至少选了两根，连同当前木棍至少有三根，不必另设数量维度。

此前 $i-1$ 根各有“选或不选”两种决定，共 $2^{i-1}$ 个下标子集。把其中总长 $S\le a_i$ 的子集扣掉，剩下的都是 $S>a_i$ 的合法子集。这里使用补集计数，是因为总子集数容易求，而只需统计较小的无效总长。

令 $f_j$ 表示此前木棍中，总长恰好为 $j$ 的子集数，初始 $f_0=1$ 。查询当前贡献后，才把当前木棍作为一件 0/1 物品加入；否则会把当前木棍既用作固定最大值又用进此前子集。只需保存到全局最大长度 $A$ ：长度都是正数，超过 $A$ 的子集和以后不会下降到某次需要扣除的范围。

逐轮手算 $[2,2,3]$ 。表中的 $f$ 只列出总长不超过全局最大长度 $A=3$ 的计数；总长 $4$ 的子集虽然不保存在数组里，仍包含在“此前全部子集”中：

当前木棍	查询前此前子集数	查询前 $(f_0,f_1,f_2,f_3)$	无效数 $S\le a_i$	本轮贡献	加入当前木棍后 $(f_0,f_1,f_2,f_3)$
第一根 $2$	$1$	$(1,0,0,0)$	$1$	$0$	$(1,0,1,0)$
第二根 $2$	$2$	$(1,0,1,0)$	$2$	$0$	$(1,0,2,0)$
第三根 $3$	$4$	$(1,0,2,0)$	$3$	$1$	$(1,0,2,1)$

处理最后的 $3$ 时，此前四个下标子集中，只有两根 $2$ 都选的总长 $4$ 大于 $3$ ，因此贡献 $1$ 。两个长度相同的 $2$ 仍分别作为两件物品处理，不能按数值去重。表格也解释了操作顺序：先查询此前子集，再把当前木棍加入 0/1 背包，否则同一根木棍会同时担任“固定的最长木棍”和“此前的一根”。

#include <bits/stdc++.h>
using namespace std;
const int N = 5010, mod = 998244353;
int n, a[N], f[N], ans, p = 1;
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
    }
    sort(a + 1, a + n + 1);
    int A = a[n];
    f[0] = 1;
    for (int i = 1; i <= n; i++)
    {
        int s = 0;
        for (int j = 0; j <= a[i]; j++)
        {
            s = (s + f[j]) % mod;
        }
        ans = (ans + p - s) % mod;
        if (ans < 0)
        {
            ans += mod;
        }
        for (int j = A; j >= a[i]; j--)
        {
            f[j] = (f[j] + f[j - a[i]]) % mod;
        }
        p = p * 2 % mod;
    }
    printf("%d\n", ans);
}

这里对 $998244353$ 取模，只表示把很大的方案数换成同余的一个代表值；加法、减法和乘 $2$ 都可先对模数取余再运算，最后把可能为负的差调整到 $[0,998244353)$ 。第十三章会完整推导取模规则。程序输入 $n$ 和 $n$ 根木棍长度，输出合法方案数的余数；要求长度均为正且至少一根。变量 $p$ 在处理第 $i$ 根前等于此前子集数 $2^{i-1}$ 的余数；每轮先查询、后更新，使 $f$ 始终只含“此前”的木棍。模数下加两个余数以及把一个余数乘 $2$ 均小于 int 上限，代码中的这些中间表达式不会溢出。排序用 $O(n\log n)$ 时间，每根木棍的查询与更新两次扫描合计为 $O(A)$ ，总时间为 $O(n\log n+nA)$ 、有效空间为 $O(n+A)$ ，数组实际按 $n,A\le5000$ 分配。

13. 本章小结与练习

遇到 DP 题时，可以依次写下：状态的精确含义、每种来源对应的最后一步、合法初值、依赖所要求的计算顺序，以及最终答案所在的位置。做空间压缩前，再确认每次更新读取的是旧层还是本层；做方案计数前，还要确认不同来源是否对应不同方案。

基础练习

最大子段和：先举出“前缀历史最优无法直接接当前项”的反例，再定义必须以当前位置结尾的状态。
过河卒：网格计数、禁止格与边界。
采药：先写二维“选/不选”的旧层来源，再解释一维倒序为什么仍读到旧层。
疯狂的采药：沿用一件耗时 $2$ 的例子，说明正序读本层为何代表允许重复选。

扩展练习

合唱队形：双向子序列状态与峰顶合并。
小 A 点菜：按下标区分的 0/1 方案计数。
石子合并（弱化版）：画出最后断点，证明短区间必须先求。
多边形：用重复长度的小例验证唯一最后位置、查询后加入及截断容量。

第十二章 动态规划入门