线性动态规划

最长上升子序列（LIS）

给定一个长度为 $N$ 的数列，求数值严格单调递增的子序列的长度最长是多少。

7
3 1 2 1 8 5 6

4

问题分析

阶段划分：按已处理序列的长度划分阶段，设阶段变量 $i$ 表示前 $i$ 个数字
设计状态：设 $f [i]$ 表示前 $i$ 个数字必须选择 $a_{i}$ 得到的最长上升子序列长度
决策：对于状态 $f [i]$ ，决策对象为 $a_{i}$ 。讨论 $a_{i}$ 与前面哪一个数构成最长上升子序列？设决策变量 $j (0 \leq j < i 且 a_{j} < a_{i})$
状态转移方程： $f [i] = m a x (f [j] + 1) (0 \leq j < i 且 a_{j} < a_{i})$
边界： $f [i] = 1 (0 \leq i < n)$
目标解： $m a x (f [i]) (0 \leq i < n)$

参考代码

cpp

#include <bits/stdc++.h>

using namespace std;

const int N = 1010;
int a[N], f[N];

int main() {
    int n; cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    for (int i = 0; i < n; i++) {
        f[i] = 1;
        for (int j = 0; j < i; j++) {
            if (a[j] < a[i]) {
                f[i] = max(f[i], f[j] + 1);
            }
        }
    }

    int ans = 0;
    for (int i = 0; i < n; i++) {
        ans = max(ans, f[i]);
    }
    cout << ans << endl;

    return 0;
}

以上代码的时间复杂度为 $O (N^{2})$ ，我们可以把它优化成 $O (N \log (N))$ 。

思路：首先数组 $a$ 中存输入的数（原本的数），开辟一个数组 $f$ 用来存结果，最终数组 $f$ 的长度就是最终的答案；假如数组 $f$ 现在存了数，当到了数组 $a$ 的第 $i$ 个位置时，首先判断 $a [i] > f [c n t]$ ？若是大于则直接将这个数添加到数组 $f$ 中，即 $f [+ + c n t] = a [i];$ 这个操作时显然的。当 $a [i] <= f [c n t]$ 的时,我们就用 $a [i]$ 去替代数组 $f$ 中的第一个大于等于 $a [i]$ 的数，因为在整个过程中我们维护的数组 $f$ 是一个递增的数组，所以我们可以用二分查找在 $l o g n$ 的时间复杂的的情况下直接找到对应的位置，然后替换，即 $f [l] = a [i]$ 。

我们用 $a [i]$ 去替代 $f [i]$ 的含义是：以 $a [i]$ 为最后一个数的严格单调递增序列,这个序列中数的个数为 $l$ 个。

这样当我们遍历完整个数组 $a$ 后就可以得到最终的结果。

cpp

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

const int maxn = 1e5 + 5;

int a[maxn], f[maxn];
int cnt;

inline int find(int x) {
    int l = 1, r = cnt;
    while(l < r) {
        int mid = l + r >> 1;
        if(f[mid] >= x) r = mid;
        else l = mid + 1;
    }

    return l;
}

int main() {
    int n; scanf("%d", &n);
    for(int i = 1; i <= n; i ++) scanf("%d", &a[i]);

    f[++cnt] = a[1];
    for(int i = 2; i <= n; i ++)
        if(a[i] > f[cnt]) f[ ++ cnt] = a[i];
        else {
            int tmp = find(a[i]);
            f[tmp] = a[i];
        }

    printf("%d\n", cnt);

    return 0;
}

例题

洛谷 P1020：导弹拦截

分析：最长不上升子序列 + 贪心

cpp

#include <iostream>
using namespace std;

const int N = 1e5 + 10;
int a[N], h[N], n, q[N];

int main() {
	while(cin >> a[n++]);
	n--;

    int cnt = 0, len = 0;
	for (int i = 0; i < n; i++) {
		int l = 0, r = len;
		while (l < r) {
			int mid = l + r + 1 >> 1;
			// 最长不上升子序列需要更改这里的条件
			if (q[mid] >= a[i]) l = mid;
			else r = mid - 1;
		}
		len = max(len, r + 1);
		q[r + 1] = a[i];

        int k = 0;
		while(k < cnt && h[k] < a[i]) k++;
		if (k == cnt) h[cnt++] = a[i];
		else h[k] = a[i];
	}

	cout << len << endl;
	cout << cnt << endl;

	return 0;
}

洛谷 P2196：挖地雷

分析：该题可以看作是最长上升子序列的变种。我们以处于的位置作为阶段， $f [i]$ 表示挖到第 $i$ 个地窖时挖出的最多地雷数。则 $f [i] = m a x (f [j]) + w [i] (1 \leq j < i, g [j] [i] = 1)$ 其中 $w [i]$ 表示第 $i$ 个地窖的地雷数， $g [j] [i]$ 表示地窖 $j$ 到地窖 $i$ 连通。边界条件： $f [1] = w [1]$ 。同时，该题要求记录路径，考虑使用 $p r e$ 数组记录前驱。

洛谷 P1091：合唱队形

分析：枚举队列中的每一个同学，作为分界点 $i$ 。合唱队形的左半部分：最长上升子序列，右半部分：最长下降子序列。考虑到数据范围 $(1 \leq i \leq k)$ 可能会出现整个序列单调递增或递减，此时出列的同学为 $0$ ，所以需要加特殊判断。再考虑到数据范围 $n \leq 100$ 不需要加优化！

cpp

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

const int N = 110;
int a[N], n, f[N];

int main() {
	cin >> n;
	for (int i = 0; i < n; i++) cin >> a[i];

	int ans = 200;
	for (int i = 1; i < n - 1; i++) {
		// 最长上升子序列
		int len1 = 0, len2 = 0;
		for (int j = 0; j < i; j++) {
			f[j] = 1;
			for (int k = 0; k < j; k++) {
				if (a[k] < a[j]) {
					f[j] = max(f[j], f[k] + 1);
				}
			}
		}
		for (int j = 0; j < i; j++) {
			len1 = max(len1, f[j]);
		}
		// cout << i << " " << len1 << " ";

		// 最长下降子序列
		for (int j = i + 1; j < n; j++) {
			f[j] = 1;
			for (int k = i + 1; k < j; k++) {
				if (a[k] > a[j]) {
					f[j] = max(f[j], f[k] + 1);
				}
			}
		}
		for (int j = i + 1; j < n; j++) {
			len2 = max(len2, f[j]);
		}
		// cout << len2 << endl;

		// 整个序列单调递增或递减
		if (len1 == i && len2 == n - i - 1) {
			if ((a[i - 1] < a[i] && a[i] < a[i + 1]) || a[i - 1] > a[i] && a[i] > a[i + 1]) {
				ans = 0;
				break;
			}
		}
		ans = min(ans, n - len1 - len2);
	}

	cout << ans << endl;

	return 0;
}

洛谷 P2782：友好城市

分析：最长上升子序列。此岸排序，考虑彼岸是最长上升子序列。数据范围较大，优化！

最长公共子序列（LCS）

给定两个长度分别为 $N$ 和 $M$ 的字符串 $A$ 和 $B$ ，求既是 $A$ 的子序列又是 $B$ 的子序列的字符串长度最长是多少。

4 5
acbd
abedc

3

问题分析

状态表示
1. 集合：所有在 A 序列前 $i$ 个元素中出现，且在 B 序列前 $j$ 元素中出现的公共子序列。
2. 属性： $f (i, j)$ 表示所有在 A 序列前 $i$ 个元素中出现，且在 B 序列前 $j$ 个元素中出现的公共子序列的长度最大值。
3. 集合划分：
  1. 选 $A [i]$ 选 $B [j]$ -> $f [i - 1] [j - 1]$
  2. 选 $A [i]$ 不选 $B [j]$ -> $f [i] [j - 1]$ 集合包含该划分且包含 $f [i - 1] [j - 1]$
  3. 不选 $A [i]$ 选 $B [j]$ -> $f [i - 1] [j]$ 集合包含该划分且包含 $f [i - 1] [j - 1]$
  4. 不选 $A [i]$ 不选 $B [j]$ -> $f [i - 1] [j - 1] + 1$
状态计算
1. 当 $A [i] = B [j]$ 时 $f (i, j) = f (i - 1, j - 1) + 1$
2. 否则， $f (i, j) = m a x {f (i - 1, j), f (i, j - 1)}$

参考代码

cpp

#include <bits/stdc++.h>

using namespace std;

const int N = 1010;
int f[N][N];
int n, m;
char a[N], b[N];

int main() {
    scanf("%d%d%s%s", &n, &m, a + 1, b + 1);

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (a[i] == b[j]) f[i][j] = f[i - 1][j - 1] + 1;
            else f[i][j] = max(f[i - 1][j], f[i][j - 1]);
        }
    }

    printf("%d\n", f[n][m]);

    return 0;
}

最长公共上升子序列

问题分析

设计状态：设 $f [i] [j]$ 表示以 $A$ 序列的前 $i$ 个元素与 $B$ 序列的前 $j$ 个元素且以 $b_{j}$ 结尾构成的最长公共上升子序列的长度
决策：对于状态 $f [i] [j]$ 考虑 $a_{i}$ 是否在最长公共上升子序列中，如果 $a_{i}$ 在该序列上，则有状态定义知： $a_{i} = b_{j}$ ，如果 $a_{i}$ 不在该序列上，则有状态定义知： $a_{i} \neq b_{j}$
状态转移方程 $f (i, j) = m a x {\begin{cases} f (i - 1, j), & a_{i} \neq b_{j} \\ m a x (f (i - 1, k)) + 1, & a_{i} = b_{j}, 1 \leq k < j, b_{k} < b_{j} \end{cases}$
目标解： $m a x (f [n] [i]) (1 \leq i \leq n)$

参考代码

cpp

#include <bits/stdc++.h>

using namespace std;

const int N = 3010;
int f[N][N];
int n;
int a[N], b[N];

int main()
{
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> a[i];
	for (int i = 1; i <= n; i++) cin >> b[i];

	// for (int i = 1; i <= n; i++) {
	// 	for (int j = 1; j <= n; j++) {
	// 		f[i][j] = f[i - 1][j];
	// 		if (a[i] == b[j]) {
	// 			f[i][j] = max(f[i][j], 1);
	// 			for (int k = 1; k < j; k++) {
	// 				if (b[k] < a[i]) f[i][j] = max(f[i][j], f[i - 1][k] + 1);
	// 			}
	// 		}
	// 	}
	// }

	// 优化
	for (int i = 1; i <= n; i++) {
		int maxv = 1; // maxv 存储 f[i - 1][k] 中的最大值
		for (int j = 1; j <= n; j++) {
			f[i][j] = f[i - 1][j];
			if (a[i] == b[j]) {
				f[i][j] = max(f[i][j], maxv);
			}
			if (b[j] < a[i]) maxv = max(maxv, f[i - 1][j] + 1);
		}
	}

	int ans = 0;
	for (int i = 1; i <= n; i++) {
		ans = max(ans, f[n][i]);
	}
	cout << ans << endl;

	return 0;
}

经典例题

洛谷 P2758：编辑距离

分析：考虑两个字符串（ $a, b$ ）处理的位置作为阶段，设 $f [i] [j]$ 表示将 $a [1 \sim i]$ 变成 $b [1 \sim j]$ 所需要的最小操作次数。

三种操作：

$a [i] = a [j]$ ： $f [i] [j] = f [i - 1] [j - 1]$
$a [i] \neq a [j]$
1. 删除： $f [i] [j] = f [i - 1] [j] + 1$ 删除 $a [i]$
2. 插入： $f [i] [j] = f [i] [j - 1] + 1$ 在 $a$ 中插入 $b [j]$
3. 更改： $f [i] [j] = f [i - 1] [j - 1] + 1$ 将 $a [i]$ 变成 $b [j]$

边界条件：

$f [i] [0] = i (0 \leq i \leq n)$ 只能删除 $i$ 次
$f [0] [i] = i (0 \leq i \leq m)$ 只能插入 $i$ 次

目标解： $f [n] [m]$

cpp

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

const int N = 2010;
char a[N], b[N];
int f[N][N]; // f[i][j] 表示将 a[1 ~ i] 变成 b[1 ~ j] 所需要的最小操作次数

int main() {
	scanf("%s", a + 1);
	scanf("%s", b + 1);
	int n = strlen(a + 1);
	int m = strlen(b + 1);

	for (int i = 0; i <= n; i++) f[i][0] = i; // 删
	for (int i = 0; i <= m; i++) f[0][i] = i; // 增

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (a[i] == b[j]) f[i][j] = f[i - 1][j - 1];
			else f[i][j] = min(f[i - 1][j - 1] + 1, min(f[i - 1][j] + 1, f[i][j - 1] + 1));
		}
	}

	printf("%d\n", f[n][m]);

	return 0;
}

洛谷 P1004：方格取数

问题：为什么不能做两次二维 DP 或是两次DFS呢？
因为第一次走的时候有可能有好几条路径都是第一次的解，而你分开走只能选择其中的一条。很不幸的是，第一次走过的地方会被重置成 $0$ ，而你不确定的是第一次同样是最优解而未被你选择的情况下第二次的值会不会比你已经得出的答案要大。

分析：两条路径同时走，以位置作为阶段，设 $f [i_{1}] [j_{1}] [i_{2}] [j_{2}]$ 表示两条路径从 $(1, 1), (1, 1)$ 分别走到 $(i_{1}, j_{1}), (i_{2}, j_{2})$ 的取数之和最大值。

考虑 $f [i_{1}] [j_{1}] [i_{2}] [j_{2}]$ 两条路径分别可以由上一位置通过 下下、下右、右下、右右 转移而来。

状态转移方程：

$(i_{1}, j_{1}) = (i_{2}, j_{2})$ ： $f (i_{1}, j_{1}, i_{2}, j_{2}) = m a x {\begin{cases} f (i_{1} - 1, j_{1}, i_{2} - 1, j_{2}) \\ f (i_{1} - 1, j_{1}, i_{2}, j_{2} - 1) \\ f (i_{1}, j_{1} - 1, i_{2} - 1, j_{2}) \\ f (i_{1}, j_{1} - 1, i_{2}, j_{2} - 1) \end{cases} + a (i_{1}, j_{1})$
$(i_{1}, j_{1}) \neq (i_{2}, j_{2})$ ： $f (i_{1}, j_{1}, i_{2}, j_{2}) = m a x {\begin{cases} f (i_{1} - 1, j_{1}, i_{2} - 1, j_{2}) \\ f (i_{1} - 1, j_{1}, i_{2}, j_{2} - 1) \\ f (i_{1}, j_{1} - 1, i_{2} - 1, j_{2}) \\ f (i_{1}, j_{1} - 1, i_{2}, j_{2} - 1) \end{cases} + a (i_{1}, j_{1}) + a (i_{2}, j_{2})$

边界：对于 $i_{1}$ 或 $j_{1}$ 有一个为 0，同时 $i_{2}$ 或 $j_{2}$ 有一个为 0，则为 0

目标解： $f [n] [n] [n] [n]$

cpp

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

const int N = 15;
int a[N][N];
int f[N][N][N][N]; // f[i1][j1][i2][j2] 表示两条路径从 (1, 1),(1,1) 分别走到 (i1, j1),(i2, j2) 的取数之和最大值
int n;

int main() {
	cin >> n;
	int x, y, z;
	while (cin >> x >> y >> z) {
		if (x == 0 && y == 0 && z == 0) break;
		a[x][y] = z;
	}

	for (int i1 = 1; i1 <= n; i1++) {
		for (int j1 = 1; j1 <= n; j1++) {
			for (int i2 = 1; i2 <= n; i2++) {
				for (int j2 = 1; j2 <= n; j2++) {
					int t1 = max(f[i1 - 1][j1][i2 - 1][j2], f[i1][j1 - 1][i2][j2 - 1]);
					int t2 = max(f[i1 - 1][j1][i2][j2 - 1], f[i1][j1 - 1][i2 - 1][j2]);
					f[i1][j1][i2][j2] = max(t1, t2) + a[i1][j1];
					if (i1 != i2 || j1 != j2) f[i1][j1][i2][j2] += a[i2][j2];
				}
			}
		}
	}

	cout << f[n][n][n][n] << endl;

	return 0;
}

本题可以降维（考虑将步数作为阶段），参见该题解

AcWing 271：杨老师的照相排列

分析：对于合法的合影方案每排每列一定是单调的，同时从上而下每排的人数也一定是单调递减的，因此我们考虑以合影方案的轮廓作为阶段。设 $f (a, b, c, d, e)$ 表示一排至第五排分别有 $(a, b, c, d, e)$ 人时的方案数。

决策与状态转移：考虑最后一个人安排在第几排？

第 1 排： $t_{1} = f (a - 1, b, c, d, e)$
第 2 排： $t_{2} = f (a, b - 1, c, d, e)$
第 3 排： $t_{3} = f (a, b, c - 1, d, e)$
第 4 排： $t_{4} = f (a, b, c, d - 1, e)$
第 5 排： $t_{5} = f (a, b, c, d, e - 1)$

则 $f (a, b, c, d, e) = t_{1} + t_{2} + t_{3} + t_{4} + t_{5}$

注意：并不是每种安排方式都合法，后一排人数需要小于前一排人数。

边界： $f (0, 0, 0, 0, 0) = 1$ ，其余都是 $0$

目标解： $f (s [1], s [2], s [3], s [4], s [5])$ ， $s [i]$ 表示第 $i$ 排人数

cpp

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

const int N = 31;
long long f[N][N][N][N][N];
int n;

int main()
{
	while (cin >> n) {
		if (n == 0) break;

		int s[5] = { 0 };
		for (int i = 0; i < n; i++) cin >> s[i];

		memset(f, 0, sizeof f);
		f[0][0][0][0][0] = 1;

		for (int a = 0; a <= s[0]; a++) {
			for (int b = 0; b <= s[1]; b++) {
				for (int c = 0; c <= s[2]; c++) {
					for (int d = 0; d <= s[3]; d++) {
						for (int e = 0; e <= s[4]; e++) {
							long long& t = f[a][b][c][d][e];
							if (a && a - 1 >= b) t += f[a - 1][b][c][d][e];
							if (b && b - 1 >= c) t += f[a][b - 1][c][d][e];
							if (c && c - 1 >= d) t += f[a][b][c - 1][d][e];
							if (d && d - 1 >= e) t += f[a][b][c][d - 1][e];
							if (e) t += f[a][b][c][d][e - 1];
						}
					}
				}
			}
		}

		cout << f[s[0]][s[1]][s[2]][s[3]][s[4]] << endl;
	}

	return 0;
}

AcWing 274：移动服务

分析：按已处理的请求作为划分阶段，状态转移时还需要考虑上一阶段三位服务员所处的位置，因此设 $f (i, x, y, z)$ 表示已处理前 $i$ 个请求，且三位服务员分别位于位置 $(x, y, z)$ 时最小花费。

状态转移：（以 DAG 思考状态转移有填表和刷表两种方式，这里使用刷表法，为什么呢？因为当前状态计算下一状态只有三种情况，比较简单）

派 $x$ 去： $f (i + 1, p [i + 1], y, z) = m i n (f (i + 1, p [i + 1], y, z), f (i, x, y, z) + w [x] [p [i + 1]])$
派 $y$ 去： $f (i + 1, x, p [i + 1], z) = m i n (f (i + 1, x, p [i + 1], z), f (i, x, y, z) + w [y] [p [i + 1]])$
派 $z$ 去： $f (i + 1, x, y, p [i + 1]) = m i n (f (i + 1, x, y, p [i + 1]), f (i, x, y, z) + w [z] [p [i + 1]])$

注： $p [i]$ 表示第 $i$ 请求的位置， $w [i] [j]$ 表示从位置 $i$ 到位置 $j$ 的花费。

提示：由于同一位置不能有两个服务员，所以状态转移时需要先判断。

考虑到题目数据范围，我们开始优化状态的表示。当我们处理第 $i$ 个请求时，某一服务员就会到达该位置 $p [i]$ ，那么我们是否可以这样表示状态：设 $f (i, x, y)$ 表示已处理前 $i$ 个请求，且一名服务员位于 $p [i]$ 另外两名服务员分别位于位置 $(x, y)$ 时最小花费。

此时 $z = p [i]$

派 $x$ 去： $f (i + 1, z, y) = m i n (f (i + 1, z, y), f (i, x, y) + w [x] [p [i + 1]])$
派 $y$ 去： $f (i + 1, x, z) = m i n (f (i + 1, x, z), f (i, x, y) + w [y] [p [i + 1]])$
派 $z$ 去： $f (i + 1, x, y) = m i n (f (i + 1, x, y), f (i, x, y) + w [z] [p [i + 1]])$

边界条件： $f (i, x, y) = + \infty, p [0] = 3, f (0, 1, 2) = 0$ 表示处理了第 $0$ 个请求，三名服务员分别位于 $(1, 2, 3)$ 时花销为 $0$

目标解： $f [m, x, y]$ ， $m$ 个请求

cpp

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

const int N= 210, M = 1010;

int w[N][N], f[M][N][N], p[M];
int n, m;

int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> w[i][j];
		}
	}
	for (int i = 1; i <= m; i++) cin >> p[i];

	memset(f, 0x3f, sizeof f);
	p[0] = 3;
	f[0][1][2] = 0;


	for (int i = 0; i < m; i++) {
		for (int j = 1; j <= n; j++) {
			for (int k = 1; k <= n; k++) {
				int x = j, y = k, z = p[i], u = p[i + 1];
				if (x == y || x == z || y == z) continue;
				f[i + 1][z][y] = min(f[i + 1][z][y], f[i][x][y] + w[x][u]);
				f[i + 1][x][z] = min(f[i + 1][x][z], f[i][x][y] + w[y][u]);
				f[i + 1][x][y] = min(f[i + 1][x][y], f[i][x][y] + w[z][u]);
			}
		}
	}

	int ans = 1e9;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			ans = min(ans, f[m][i][j]);
		}
	}

	cout << ans << endl;

	return 0;
}

线性动态规划 ​

问题分析 ​

参考代码 ​

例题 ​

最长公共子序列（LCS） ​

问题分析 ​

参考代码 ​

问题分析 ​

参考代码 ​

经典例题 ​

线性动态规划

问题分析

参考代码

例题

最长公共子序列（LCS）

问题分析

参考代码

问题分析

参考代码

经典例题