第十四章 线性动态规划
顾名思义，线性动态规划指的是一类状态定义与题设内容线性相关的动态规划。线性状态动态规划定义状态的时候经常会考虑 “某类有序时间中前若干个子时间的答案”。
一般来说，线性的状态最为直观，容易用有向无环图（$\text{DAG}$）表示，也比较容易理解。所以遇到动态规划问题构造状态时，通常会最优先考虑能否采用线性状态。
单序列问题
例1：P1020 [NOIP1999 普及组] 导弹拦截
用 $f_i$ 表示，只考虑前 $i$ 个数，并且以第 $i$ 个数结尾的子序列长度。
for (int i = 1; i <= n; i++) {
f[i] = 1;
for (int j = 1; j < i; j++) {
if (a[i] <= a[j]) {
f[i] = std::max(f[i], f[j] + 1);
}
}
ans = std::max(ans, f[i]);
}
for (int i = 1; i <= n; i++) f[i] = 0;
for (int i = 1; i <= n; i++) {
f[i] = 1;
for (int j = 1; j < i; j++) {
if (a[i] > a[j]) {
f[i] = std::max(f[i], f[j] + 1);
}
}
cnt = std::max(cnt, f[i]);
}
例2：P2285 [HNOI2004]打鼹鼠
用 $f_i$ 表示只考虑前 $i$ 只老鼠，并且确定打了第 $i$ 只老鼠的情况下，最多能打多少只老鼠。
for (int i = 1; i <= m; i++) {
f[i] = 1;
for (int j = 1; j < i; j++) {
if (std::abs(x[i] - x[j]) + std::abs(y[i] - y[j]) <= t[i] - t[j]) {
f[i] = std::max(f[i], f[j] + 1);
}
}
ans = std::max(ans, f[i]);
}
“子序列提取” 问题的常规思路：考虑新加入的数和前面某个状态之间的关系和转移可行性，如果恰好转移只和相邻两数相关，那么就可以获得一个复杂度至多为 $\mathcal O(n^2)$ 的动态规划。
例3：P1725 琪露诺
用 $f_i$ 表示从起点出发到格子 $i$ 的最大数字和。
for (int i = L; i <= N; i++) {
while (!icy.empty() && icy.front() < i - R) icy.pop_front();
while (!icy.empty() && F[icy.back()] < F[i - L]) icy.pop_back();
icy.push_back(i - L);
F[i] = F[icy.front()] + A[i];
if (i + R > N) ans = std::max(ans, F[i]);
}
数据结构优化动态规划通常是有迹可循的，即你是十分清楚你需要一个支持什么操作的数据结构。这类题的动态规划部分相对思考难度较低，考察点一般是数据结构的应用。
例4：P4933 大师
用 $f_{i, d + maxV}$ 表示以第 $i$ 个数结尾，公差为 $d$ 的子序列的个数。
for (int i = 1; i <= n; i++) {
for (int j = 1; j < i; j++) {
f[i][h[i] - h[j] + maxV] = (f[i][h[i] - h[j] + maxV] + f[j][h[i] - h[j] + maxV] + 1) % mod;
ans = (ans + f[j][h[i] - h[j] + maxV] + 1) % mod;
}
}
std::cout << (ans + n) % mod;
例5：P1874 快速求和
记 $f_{i, s}$ 表示只使用字符串前 $i$ 位，达到数字和恰为 $s$ 的最少加号数。
std::memset(f, 0x3f, sizeof(f));
f[0][0] = -1;
for (int i = 1; i <= s.size(); i++) {
for (int j = 1; j <= i; j++) {
t[j][i] = t[j][i - 1] * 10 + s[i - 1] - '0';
}
}
for (int i = 1; i <= s.size(); i++) {
for (int k = 0; k <= n; k++) {
for (int j = i - 1; j >= 0; j--) {
if (k >= t[j + 1][i]) {
f[i][k] = std::min(f[i][k], f[j][k - t[j + 1][i]] + 1);
}
}
}
}
if (f[s.size()][n] == 0x3f3f3f3f) f[s.size()][n] = -1;
多序列问题
例6：最常公共子序列
给出两个字符串 $a, b$，求他们的最长公共子序列，字符串长度不超过 $2000$。
用 $f_{i, j}$ 表示字符串 $a$ 前 $i$ 个字符与字符串 $b$ 前 $j$ 个字符的最长公共子序列长度。
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
f[i][j] = std::max(f[i - 1][j], f[i][j - 1]);
if (a[i - 1] == b[j - 1]) {
f[i][j] = std::max(f[i][j], f[i - 1][j - 1] + 1);
}
}
}
例7：P2758 编辑距离
用 $f_{i, j}$ 表示将字符串 $a$ 前 $i$ 个字符完全转换成字符串 $b$ 前 $j$ 个字符的最少操作次数。
for (int i = 1; i <= n; i++) f[i][0] = i;
for (int j = 1; j <= m; j++) f[0][j] = j;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
f[i][j] = std::min(f[i - 1][j], f[i][j - 1]) + 1;
if (a[i - 1] != b[j - 1]) {
f[i][j] = std::max(f[i][j], f[i - 1][j - 1] + 1);
}
}
}
例8：P1439 【模板】最长公共子序列
对于两个排列的 $\text{LCS}$，可以使用一个技巧把它转化为 $\text{LIS}$。
struct BinaryIndexedTree {
int node[maxN + 10];
void Add(int pos, int val) {
while (pos <= n) {
node[pos] = std::max(node[pos], val);
pos += lowbit(pos);
}
return;
}
int Ask(int pos) {
int ret = 0;
while (pos >= 1) {
ret = std::max(ret, node[pos]);
pos -= lowbit(pos);
}
return ret;
}
} BIT;
for (int i = 1; i <= n; i++) {
f[i] = BIT.Ask(P[P1[i]]) + 1;
BIT.Add(P[P1[i]], f[i]);
ans = std::max(ans, f[i]);
}
例9：P2679 [NOIP2015 提高组] 子串
记 $f_{k, i, j}$ 表示字符串 $A$ 以 $i$ 个字符结尾取出 $k$ 段后，在字符串 $B$ 恰好匹配到 $j$ 的方案数。
首先看起来 $f_{k, i, j}$ 大部分情况都是 $0$，除非 $A_i = B_j$。那么问题就在于，当 $A_i = B_j$ 时到底会发生什么。情况很简单：$A_i$ 要么跟在上一段后面，要么新起了一段。情况一比较简单，既然段数没变，那么前继的段数还是保持 $k$，在字符串的指针也刚好是 $i - 1$ 和 $j - 1$。但情况二就会稍微复杂一点了，前继的段数应该是 $k - 1$ 没有问题，在字符串 $B$ 里的指针是 $j - 1$ 也没有问题，但是在字符串 $A$ 里的指针可以追溯到任何一个 $i$ 之前的位置。
用 $g_{k, i, j}$ 表示取出 $K$ 段后，字符串 $A$ 在 $i$ 之前结尾，字符串 $B$ 匹配到 $j$ 的方案数，很明显，这里 $g$ 是 $f$ 在第二位上的前缀和，即 $g_{k, i, j} = \sum_{x = 1}^i f_{k, x, j}$。
for (int l = 1; l <= k; l++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (a[i] == b[j]) {
f[l][i][j] = (f[l][i - 1][j - 1] + g[l - 1][i - 1][j - 1]) $ mod;
g[l][i][j] = (g[l][i - 1][j] + f[l][i][j]) % mod;
}
}
}
}
高维问题
例10：三倍经验
又一个数字金字塔，同时有 $k (k \le n)$ 次机会将上面的任意一个数乘以 $3$（不能对同一个数重复乘），最大化从最高点到底部任意一点的最大数字和。每一步可以走到左下方的点也可以到达右下方的点。层数 $n \le 100$。
把乘 $3$ 视作一种技能，把技能的使用次数也加入阶段。
用 $f_{i, j, k}$ 表示从第 $i$ 行第 $j$ 列出发到最底层，恰使用了 $k$ 次乘 $3$ 的最大数字和。那么在每个点，它的前继状态（对应原题的下一步）有 $4$ 个选项：走左下不乘 $3$，走右下不乘 $3$，走左下乘 $3$，走右下乘 $3$。分别对应了四个局面：$f_{i + 1, j, k} + a_{i, j}$，$f_{i + 1, j + 1, k} + a_{i, j}$，$f_{i + 1, j, k - 1} + 3 a_{i, j}$ 和 $f_{i + 1, j + 1, k - 1} + 3 a_{i, j}$。
for (int j = 1; j <= n; j++) {
f[n][j][0] = a[n][j];
f[n][j][1] = a[n][j] * 3;
}
for (int i = n - 1; i >= 1; i--) {
for (int j = 1; j <= i; j++) {
for (int k = 0; k <= K; k++) {
f[i][j][k] = std::max(f[i + 1][j][k], f[i + 1][j + 1][k]) + a[i][j];
if (k >= 1) {
f[i][j][k] = std::max(f[i][j][k], f[i + 1][j][k - 1] + a[i][j] * 3);
f[i][j][k] = std::max(f[i][j][k], f[i + 1][j + 1][k - 1] + a[i][j] * 3);
}
}
}
}
for (int k = 0; k <= K; k++) ans = std::max(ans, f[1][1][k]);
例11：P1004 [NOIP2000 提高组] 方格取数
记 $s = i + j = k + l$，相当于市走过的步数（加 $2$），用状态 $f_{x, i, k}$ 表示走了 $s - 2$ 步以后路径 $1$ 在第 $i$ 行（第 $s - i$ 列），路径 $2$ 在第 $k$ 行（第 $s - k$ 列），就能不带冗余地表示出所有需要的状态了。
for (int s = 2; s <= n + m; s++) {
for (int i = std::max(s - m, 1); i <= std::min(n, s - 1); i++) {
for (int k = std::max(s - m, 1); k <= std::min(n, s - 1); k++) {
f[s][i][k] = f[s - 1][i][k];
f[s][i][k] = std::max(f[s][i][k], f[s - 1][i - 1][k - 1]);
f[s][i][k] = std::max(f[s][i][k], f[s - 1][i][k - 1]);
f[s][i][k] = std::max(f[s][i][k], f[s - 1][i - 1][k]);
if (i != k) {
f[s][i][k] += a[i][s - i] + a[k][s - k];
} else {
f[s][i][k] += a[i][s - i];
}
}
}
}