0x51 线性 DP

在本书中，具有线性“阶段”划分的动态规划算法被统称为线性 $\mathrm{DP}^{\text{①}}$ 。读者对于最长上升子序列（LIS）、最长公共子序列（LCS）、数字三角形（IOI1994）等DP的经典入门例题应该并不陌生，在动态规划的入门书籍或者网络上很容易找到这些问题的描述和解答。本书不会花费时间再次详细解释这些问题，但本着见微知著的思想，我们可以简单回顾它们，并尝试分析一下DP要素在其中的体现。

容易发现，无论状态表示是一维还是多维，DP算法在这些问题上都体现为“作用

在线性空间上的递推”——DP的阶段沿着各个维度线性增长，从一个或多个“边界点”开始有方向地向整个状态空间转移、扩展，最后每个状态上都保留了以自身为“目标”的子问题的最优解。

这几个问题也是线性DP中最简单的一类，在这类问题中，需要计算的对象表现出明显的维度以及有序性，每个状态的求解直接构成一个阶段，这使得DP的状态表示就是阶段的表示。因此，我们只需要在每个维度上各取一个坐标值作为DP的状态，自然就可以描绘出“已求解部分”在状态空间中的轮廓特征，该轮廓的进展就是阶段的推移。另外，每个状态的求解显然只与之前阶段的最优解有关，最优子结构性质也得以验证。接下来，我们按顺序依次循环每个维度，根据问题要求递推求解的具体实现过程也就顺理成章了。

【例题】Mr. Young's Picture Permutations POJ2279

有 $N$ 个学生合影，站成左端对齐的 $k$ 排，每排分别有 $N_{1}, N_{2}, \dots, N_{k}$ 个人，第 1 排站在最后边，第 $k$ 排站在最前边。学生的身高互不相同，把他们从高到低依次标记为 $1, 2, \dots, N$ 。在合影时要求每一排从左到右身高递减，每一列从后到前身高也递减，问一共有多少种安排合影位置的方案？ $N \leq 30, k \leq 5$ 。

下面的一排三角矩阵给出了当 $N = 6, k = 3, N_1 = 3, N_2 = 2, N_3 = 1$ 时的全部16种合影方案，注意身高最高的是1，最低的是6。

因为在合法的合影方案中每行、每列的身高都是单调的，所以我们可以从高到低依次考虑标记为 $1,2,\dots ,N$ 的学生站的位置。这样一来，在任意时刻，已经安排好位置的学生在每一行中占据的一定是从左端开始的连续若干个位置，用一个 $k$ 元组 $(a_{1},a_{2},\dots ,a_{k})$ 表示每一行已安排的学生人数，即可描绘出“已经处理的部分”的轮廓。

当安排一名新的学生时，我们考虑所有满足如下条件的行号 $i$

1. $a_{i} < N_{i}$

2. $i = 1$ 或 $a_{i - 1} > a_i$

只要该学生站在这样一行中，每列学生的身高单调性也就得以满足。换言之，我们不需要关心已经站好的 $(a_{1} + a_{2} + \dots + a_{k})$ 名学生的具体方案。 $k$ 元组 $(a_{1}, a_{2}, \dots, a_{k})$ 描绘的轮廓内的合影方案总数就足以构成一个子问题。因此，我们可以把 $a_{1}, a_{2}, \dots, a_{k}$ 作为阶段，当安排一名新的学生时， $a_{1}, a_{2}, \dots, a_{k}$ 其中之一会增加 1，从而转移到后续的阶段，符合各维度线性增长的形式。

简便起见，我们假设 $k = 5$ 。当 $k < 5$ 时，我们可以增加人数为0的排，使其等

价于 $k = 5$ 的问题。动态规划算法如下：

$F[a_{1},a_{2},a_{3},a_{4},a_{5}]$ 表示各排从左端起分别站了 $a_1,a_2,a_3,a_4,a_5$ 个人时，合影方案数量。

边界： $F[0,0,0,0,0] = 1$ ，其余均为0。

目标： $F[N_{1},N_{2},N_{3},N_{4},N_{5}]$

转移：若 $a_1 < N_1$ ，则令 $F[a_1 + 1, a_2, a_3, a_4, a_5] + = F[a_1, a_2, a_3, a_4, a_5]$ 。若 $a_2 < N_2$ 且 $a_1 > a_2$ ，则令 $F[a_1, a_2 + 1, a_3, a_4, a_5] + = F[a_1, a_2, a_3, a_4, a_5]$ 。第 $3 \sim 5$ 排同理。

本题还有一种数学解法：直接用“杨氏矩阵”和“勾长公式”进行计算。这里就不再赘述，感兴趣的读者可以查阅相关资料。

从该题给出的解法中我们发现，设计动态规划的状态转移方程，不一定要以“如何计算出一个状态”的形式给出，也可以考虑“一个已知状态应该更新哪些后续阶段的未知状态”。当然，对于本题来讲，两种方式没有什么差别。在有的题目中，其中一种可能会比另一种思考起来更加自然、简便。

【例题】LCIS（最长公共上升子序列）TYVJ1071

熊大妈的奶牛在小沐沐的熏陶下开始研究信息题目。小沐沐先让奶牛研究了最长上升子序列，再让他们研究了最长公共子序列，现在又让他们研究最长公共上升子序列了。

小沐沐说，对于两个数列 $A$ 和 $B$ ，如果它们都包含一段位置不一定连续的数，且数值是严格递增的，那么称这一段数是两个数列的公共上升子序列，而所有的公共上升子序列中最长的就是最长公共上升子序列了。

奶牛半懂不懂，小沐沐要你来告诉奶牛什么是最长公共上升子序列。不过，只要告诉奶牛它的长度就可以了。数列 $A$ 和 $B$ 的长度均不超过3000。

这道题目是LIS与LCS的综合。请读者回顾在本节开头部分列举的LIS与LCS问题的动态规划状态表示，把二者相结合，容易想到以下解法：

$F[i,j]$ 表示 $A_{1} \sim A_{i}$ 与 $B_{1} \sim B_{j}$ 可以构成的以 $B_{j}$ 为结尾的 LCIS 的长度。不妨假设 $A_{0} = B_{0} = -\infty$ 。

当 $A_{i}\neq B_{j}$ 时，有 $F[i,j] = F[i - 1,j]$

当 $A_{i} = B_{j}$ 时，有

显然，上面的状态转移方程可以直接用三重循环的程序计算（初始化部分省略）。

if  $(a[i] == b[j])$  { for(int  $k = 0;k <   j;k + + )$  if  $(b[k] <   a[i])$  （20  $f[i][j] = \max (f[i][j],f[i - 1][k] + 1);$  1} else  $f[i][j] = f[i - 1][j];$

在转移过程中，我们把满足 $0 \leq k < j, B_{k} < A_{i}$ 的 $k$ 构成的集合称为 $F[i,j]$ 进行状态转移时的决策集合，记为 $S(i,j)$ 。注意到，在第二层循环 $j$ 从1增加到 $m$ 时，第一层循环 $i$ 是一个定值，这使得条件 $B_{k} < A_{i}$ 是固定的。因此，当变量 $j$ 增加1时， $k$ 的取值范围从 $0 \leq k < j$ 变为 $0 \leq k < j + 1$ ，即整数 $j$ 可能会进入新的决策集合。也就是说，我们只需要0(1)地检查条件 $B_{j} < A_{i}$ 是否满足，已经在决策集合中的数则一定不会被去除：

所以，上面的状态转移方程只需要两重循环即可求解。

for (int i = 1; i <= n; i++) { // val 是决策集合 S(i, j) 中 f[i-1][k] 的最大值 int val = 0; // j=1 时，0 可以作为 k 的取值 if (b[0] < a[i]) val = f[i - 1][0]; for (int j = 1; j <= m; j++) { if (a[i] == b[j]) f[i][j] = val + 1; else f[i][j] = f[i - 1][j]; // j 即将增大为 j+1，检查 j 能否进入新的决策集合 if (b[j] < a[i]) val = max(val, f[i - 1][j]); }

这道题转移部分的优化告诉我们，在实现状态转移方程时，要注意观察决策集合的范围随着状态的变化情况。对于“决策集合中的元素只增多不减少”的情景，就可以像本题一样维护一个变量来记录决策集合的当前信息，避免重复扫描，把转移的复杂度降低一个量级。

【例题】Making the Grade FOJ3666

给定长度为 $N$ 的序列 $A$ ，构造一个长度为 $N$ 的序列 $B$ ，满足：

1. $B$ 非严格单调，即 $B_{1} \leq B_{2} \leq \dots \leq B_{N}$ 或 $B_{1} \geq B_{2} \geq \dots \geq B_{N}$ 。

2. 最小化 $S = \sum_{i=1}^{N} |A_i - B_i|$ 。

只需要求出这个最小值 $S$ 。 $1 \leq N \leq 2000, 1 \leq |A_i| \leq 10^9$ 。

序列 $B$ 可能有“非严格单调递增”和“非严格单调递减”两种情况，我们分别进行一次求解，二者的结果中较小的就是本题的答案。下面以递增为例进行讲解，递减同理。

引理

在满足 $S$ 最小化的前提下，一定存在一种构造序列 $B$ 的方案，使得 $B$ 中的数值都在 $A$ 中出现过。

证明：

数学归纳法。命题对 $N = 1$ 显然成立。

设引理对 $N = k - 1$ 成立，此时构造出的序列为 $B_{1} \sim B_{k - 1}$ 。

当 $N = k$ 时，若 $B_{k - 1}\leq A_k$ ，则令 $B_{k} = A_{k}$ ，满足单调性且命题仍成立。

否则，要么令 $B_{k} = B_{k - 1}$ ，命题仍成立。要么存在一个 $j$ ，令 $B_{j},B_{j + 1},\dots ,B_{k}$ 为同一个值 $\mathcal{V}$ 。根据第0x05节中提到的“货仓选址”问题，设 $A_{j},A_{j + 1},\dots ,A_{k}$ 的中位数是mid，若 $mid\geq B_{j - 1}$ ，则有 $v = mid$ ，否则应该有 $v = B_{j - 1}$ 。无论哪种情况， $B_{1}\sim B_{k}$ 中的数都在 $A$ 中出现过。

证毕。

回到本题。我们依次考虑：完成前 $i(1 \leq i \leq N)$ 个数的构造时， $\sum_{j=1}^{i} |A_j - B_j|$ 的最小值。也就是把 DP 的“阶段”设为已经处理完的前缀序列的长度。在转移时，为了确定 $B_i$ 定为多少才能保证单调，我们还需要知道 $B_{i-1}$ 的大小。有两种常见的解决方案：

方法一

仿照LIS问题，设 $F[i]$ 表示完成前 $i$ 个数的构造，并且 $B_{i} = A_{i}$ 时， $S$ 的最小值。

其中， $cost(j + 1, i - 1)$ 表示构造 $B_{j+1}, \dots, B_{i-1}$ 同时满足 $A_j \leq B_{j+1} \leq \dots \leq B_{i-1} \leq A_i$ 时， $\sum_{k=j+1}^{i-1} |A_k - B_k|$ 的最小值。

该解法的思路是，根据引理可知，最终 $B$ 序列由一段段 $A$ 中的数构成。上面DP中的 $i$ 就是当前最新的一段数中与 $A$ 相同的位置， $j$ 是上一段数中这样的位置。因此， $\operatorname{cost}(j + 1, i - 1)$ 就是把区间 $[j + 1, i - 1]$ 中前面的一部分变为 $A_j$ ，后面的一部分变为 $A_i$ ，所需要的最小代价。

注意，我们不需要考虑存在一个 $k \in [j + 1, i - 1]$ ， $[j + 1, i - 1]$ 中的一部分数变为 $A_k$ 的情况，因为该情况已经在 $j = k$ 时被上述DP方程涵盖。

采用朴素算法计算cost值，总的时间复杂度为 $O(N^3)$

方法二

既然仅把DP的“阶段”要素（即已经处理的序列长度）放在DP状态中不足以执行转移，一个直接的想法就是把 $B$ 序列的最后一个值也记录在DP状态里。设 $F[i,j]$ 表示完成前 $i$ 个数的构造，其中 $B_{i} = j$ 时， $S$ 的最小值。

根据引理，我们可以把 $A$ 序列中出现的数进行离散化，把DP状态中第二维 $j$ 的范围降低到 $O(N)$ 。另外，本题的转移与上一道例题LCIS非常相似，决策集合只增多不减少，0(1)即可实现转移。故该算法的时间复杂度为 $O(N^{2})$ 。

【思考题】

把一个序列 $A$ 变成非严格单调递增的（单调不下降的），至少需要修改多少个数？

提示：序列 $A$ 的总长度减去 $A$ 的最长不下降子序列长度。

把一个序列 $A$ 变成严格单调递增的，至少需要修改多少个数？

提示：构造序列 $B[i] = A[i] - i$ ，答案为序列总长度减去 $B$ 的最长不下降子序列长度。

请读者思考：为什么这样是正确的？为什么用序列总长度减去 $A$ 的LIS长度不对？

【例题】Mobile Service TYVJ1061

一个公司有三个移动服务员，最初分别在位置1，2，3处。

如果某个位置 (用一个整数表示) 有一个请求, 那么公司必须指派某名员工赶到那个地方去。某一时刻只有一个员工能移动, 且不允许在同样的位置出现两个员工。从 $p$ 到 $q$ 移动一个员工,需要花费 $c\left( {p,q}\right)$ 。这个函数不一定对称,但保证 $c\left( {p,p}\right) = 0$ 。

给出 $N$ 个请求，请求发生的位置分别为 $p_1 \sim p_N$ 。公司必须按顺序依次满足所有请求，目标是最小化公司花费，请你帮忙计算这个最小花费。 $N \leq 1000$ ，位置是 $1 \sim 200$ 的整数。

使用动态规划解决本题，容易发现DP的“阶段”就是“已经完成的请求数量”，通过指派一名服务员，可以把一个“完成 $i - 1$ 个请求”的状态转移到“完成 $i$ 个请求”的状态。

为了计算指派服务员的花费，就必须要知道状态转移时每个服务员的位置。最直接的想法就是把三个服务员的位置也放在DP的“状态”中。设 $F[i, x, y, z]$ 表示：完成

了前 $i$ 个请求，三个员工分别位于 $x, y, z$ 时，公司当前最小花费。

考虑 $F[i, x, y, z]$ 能够更新 $i + 1$ 阶段的哪些状态。转移显然有三种，就是派三个员工之一去第 $i + 1$ 个请求处。

该算法的规模大约在 $1000 * 200^{3}$ ，不能承受。仔细观察可以发现，在第 $i$ 个请求完成时，一定有某个员工位于位置 $p_{i}$ ，只需要知道阶段 $i$ 和另外两个员工的位置即可描述一个状态，处于 $p_{i}$ 的员工位置对 DP 来说是冗余信息。

因此，可用 $F[i, x, y]$ 表示完成了前 $i$ 个请求，其中一个员工位于 $p_i$ ，另外两个员工位于 $x$ 和 $y$ 时，公司当前最小花费。

三种转移则分别是让位于 $p_i, x$ 和 $y$ 的员工前往 $p_{i+1}$ 处理请求。

不妨设 $p_0 = 3$ ，于是初值可设为 $F[0,1,2] = 0$ ，目标为 $F[N,?,?]$ 。

这道题给我们两点启发：

1. 求解线性DP问题，一般先确定“阶段”。若“阶段”不足以表示一个状态，则可以把所需的附加信息也作为状态的维度。

在转移时，若总是从一个阶段转移到下一个阶段（本题 $i$ 到 $i + 1$ ），则没有必要关心附加信息维度的大小变化情况（本题 $x, y, z$ 在转移前后大小不定），因为无后效性已经由“阶段”保证。

1. 在确定 DP 状态时，要选择最小的能够覆盖整个状态空间的“维度集合”。

若DP状态由多个维度构成，则应检查这些维度之间能否相互导出，用尽量少的维度覆盖整个状态空间，排除冗余维度。可以类比第0x36节中提到的“线性无关组”。例如本题，阶段 $i$ 和两个员工位置就可表明状态，另一个员工的位置可直接得出。

【例题】传纸条 NOIP2008/CODEVS1169

给定一个 $N * M$ 的矩阵 $A$ ，每个格子中有一个整数。现在需要找到两条从左上角(1,1)到右下角 $(N, M)$ 的路径，路径上的每一步只能向右或向下走。路径经过的格子中的数会被取走，若两条路径同时经过一个格子，只算一次。求取得的数之和最大是多少。 $N, M \leq 50$ 。

首先尝试寻找一个线性的“阶段”。考虑路径形成的过程，我们需要从左上角开始依次确定两条路径上的每一步如何走，直至到达右下角。把路径与前面问题中的序列相类比，自然想到可以把“路径长度”，即当前走过的步数，作为DP的“阶段”。在每个阶段中，我们把两条路径同时扩展一步，路径长度增加1，从而转移到下一个阶段。

除了“路径长度”外，还需要确定两条路径当前的末尾位置。设路径长度为 $i$ ，第一条路径末尾位于 $(x_{1},y_{1})$ ，第二条路径末尾位于 $(x_{2},y_{2})$ 。根据上一道例题的启发，为了找到能够覆盖整个状态空间的最小的“维度集合”，我们检查上面五个值有何种关系，能否互相导出。容易发现有以下等式成立：

故 $i, x_{1}, y_{1}$ 三个维度即可描述一个状态。

设 $F[i, x_1, x_2]$ 表示两条路径长度均为 $i$ ，第一条路径末尾在第 $x_1$ 行，第二条路径末尾在第 $x_2$ 行时，已经取得的数之和的最大值。此时可推出 $y_1 = i + 2 - x_1$ ， $y_2 = i + 2 - x_2$ 。

每条路径有向右、向下两种扩展方法，故共有 $2 * 2 = 4$ 种转移。以两条路径均往右扩展为例，其余三种情况同理。

如果 $x_{1} = x_{2}$ 并且 $y_{1} + 1 = y_{2} + 1$ ，那么两条路径进入同一个格子，只累加一次：

否则两条路径分别扩展到不同的格子，两个格子中的数都进行累加：

初值为 $F[0,1,1] = \mathrm{A}[1,1]$ 。

目标为 $F[N + M - 2,N,N]$

*【例题】I-country SGU167

在 $N * M$ 的矩阵中，每个格子有一个权值，要求寻找一个包含 $K$ 个格子的凸连通块（连通块中间没有空缺，并且轮廓是凸的，如右图所示），使这个连通块中的格子的权值和最大。求出这个最大的权值和，并给出连通块的具体方案。 $N, M \leq 15, K \leq 225$ 。

任何一个凸连通块可以划分成连续的若干行，每行的左端点列号先递减、后递增，右端点列号先递增、后递减。我们可以依次考虑从 $N * M$ 矩阵的每一行中选择哪些格子来构成所求的凸连通块。需要关注的信息有：

1. 当前已经处理完的行数。

2. 已经选出的格子数。

3. 当前行已选格子的左端位置——为了确定下一行左端点的范围，以满足单调性。

4. 当前行已选格子的右端位置——为了确定下一行右端点的范围，以满足单调性。

5. 当前左侧轮廓的单调性类型——列号是该递增还是递减。

6. 当前右侧轮廓的单调性类型——列号是该递增还是递减。

行数和格子数可以作为DP的“阶段”，每次转移到下一行，同时选出的格子数增加，在这两个维度上都符合“阶段线性增长”的特点。因此，可以设计以下的状态表示：

$F[i,j,l,r,x,y]$ 表示前 $i$ 行选了 $j$ 个格子，其中第 $i$ 行选择了第 $l$ 到 $r$ 个格子（若不选则均为0），左边界的单调性类型为 $x$ ，右边界的单调性类型为 $y$ （0表示递增，1表示递减）时，能构成的凸连通块的最大权值和。

状态转移方程：

1. 左边界列号递减，右边界列号递增（两个边界都处于扩张状态）。

2.左、右边界列号都递减（左边界扩张，右边界收缩）。

3.左、右边界列号都递增（左边界收缩，右边界扩张）。

1. 左边界列号递增，右边界列号递减（两个边界都处于收缩状态）。

初态： $F[i,0,0,0,1,0] = 0$

目标： $\max \{F[i,K,l,r,x,y]\}$

时间复杂度： $O(NM^4 K) = O(N^2 M^5)$

本题还要输出方案。在动态规划问题需要给出方案时，通常做法是额外使用一些与DP状态大小相同的数组记录下来每个状态的“最优解”是从何处转移而来的。最终，在DP求出最优解后，通过一次递归，沿着记录的每一步“转移来源”回到初态，即可

得到一条从初态到最优解的转移路径，也就是所求的具体方案。

【例题】Cookies

圣诞老人共有 $M$ 个饼干，准备全部分给 $N$ 个孩子。每个孩子有一个贪婪度，第 $i$ 个孩子的贪婪度为 $\mathrm{g}[i]$ 。如果有 $a[i]$ 个孩子拿到的饼干数比第 $i$ 个孩子多，那么第 $i$ 个孩子会产生 $\mathrm{g}[i] * a[i]$ 的怨气。给定 $N$ 、 $M$ 和序列 $\mathbf{g}$ ，圣诞老人请你帮他安排一种分配方式，使得每个孩子至少分到一块饼干，并且所有孩子的怨气总和最小。 $1 \leq N \leq 30, N \leq M \leq 5000$ 。

在这道题目中，“已经获得饼干的孩子数”和“已经发放的饼干数”显然应该作为DP的“阶段”。不过，一个孩子的怨气大小与其他孩子获得的饼干数有关，这让我们很难对状态进行划分以产生“子结构”，同时也很难计算出每个孩子的怨气值。

仔细思考可以发现，贪婪度大的孩子应该获得更多的饼干。读者用 $0 \times 07$ 节贪心算法中邻项交换的方法很容易证明这一点。因此，可以把 $N$ 个孩子按照贪婪度从大到小排序，他们分配到的饼干数将是单调递减的。

设 $F[i,j]$ 表示前 $i$ 个孩子一共分配 $j$ 块饼干时，这 $i$ 个孩子的怨气总和的最小值。直观的思想是考虑分给第 $i + 1$ 个孩子多少块饼干，然后进行转移。转移时有两种情况：

1. 第 $i + 1$ 个孩子获得的饼干数比第 $i$ 个孩子少，此时 $a[i + 1] = i$ 。

2. 第 $i + 1$ 个孩子获得的饼干数与第 $i$ 个孩子相同，此时还需要知道 $i$ 前面有几个孩子与 $i$ 获得的饼干数也相同，才能计算出 $a[i + 1]$ 。

总而言之，无论哪种情况，我们都需要知道第 $i$ 个孩子获得的饼干数，以及 $i$ 前面有多少个孩子与 $i$ 获得的饼干数相同，如下图所示。然而，在现有的DP状态下，很难高效地维护这两种信息。

观察图中的形状，我们不妨对状态转移做一个等价转换。

1. 若第 $i$ 个孩子获得的饼干数大于 1, 则等价于分配 $j - i$ 个饼干给前 $i$ 个孩子, 每人少拿一块饼干, 获得的饼干数的相对大小顺序不变, 从而怨气之和也不变。

1. 若第 $i$ 个孩子获得的饼干数为1，则枚举 $i$ 前面有多少个孩子也获得1块饼干。

整个DP算法的状态转移方程：

初态： $F[0,0] = 0$ ，目标： $F[N,M]$ 。

这道题启发我们，有时可以通过额外的算法确定DP状态的计算顺序，有时可以在状态空间中运用等效手法对状态进行缩放。在本题中，我们就利用贪心策略，在DP前对 $N$ 个孩子执行排序，使他们获得的饼干数单调递减。我们还利用相对大小的不变性，把第 $i + 1$ 个孩子获得的饼干数先缩放到1，再考虑 $i$ 前面有几个孩子获得的饼干数量相等，使需要计算的问题得到了极大的简化，容易进行维护、转移。