第五章 动态规划二
线性DP
状态转移方程呈现出一种线性的递推形式的DP，我们将其称为线性DP。
数字三角形
给定一个如下图所示的数字三角形，从顶部出发，在每一结点可以选择移动至其左下方的结点或移动至其右下方的结点，一直走到底层，要求找出一条路径，使路径上的数字的和最大。
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
输入格式
第一行包含整数 n，表示数字三角形的层数。
接下来 n 行，每行包含若干整数，其中第 i 行表示数字三角形第 i 层包含的整数。
输出格式
输出一个整数，表示最大的路径数字和。
数据范围
1≤n≤500,
−10000≤三角形中的整数≤10000
输入样例：
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
输出样例：
30
分析
f[i][j] = max(f[i - 1][j - 1], f[i - 1][j]) + a[i][j]
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 510, INF = 1e9;
int a[N][N], f[N][N];
int main() {
int n;
cin >> n;
for (int i= 1; i <= n; i++)
for (int j = 1; j <= i; j++)
cin >> a[i][j];
for (int i= 0; i <= n; i++)
for (int j = 0; j <= i + 1; j++)
f[i][j] = -INF;
f[1][1] = a[1][1];
for (int i = 2; i <= n; i++)
for (int j = 1; j <= i; j++)
f[i][j] = max(f[i - 1][j - 1], f[i - 1][j]) + a[i][j];
int res = -INF;
for (int i = 1; i <= n; i++) res = max(res, f[n][i]);
cout << res << endl;
return 0;
}
这道题还可以从下往上递推，考虑f[i][j]来自左下方和来自右下方两种情况，这样就不需要处理边界问题，而且最后的结果一定集中在f[1][1]中。
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 510, INF = 1e9;
int a[N][N], f[N][N];
int main() {
int n;
cin >> n;
for (int i= 1; i <= n; i++)
for (int j = 1; j <= i; j++)
cin >> a[i][j];
for (int i = 1; i <= n; i++) f[n][i] = a[n][i];
for (int i = n - 1; i >= 1; i--)
for (int j = 1; j <= i; j++)
f[i][j] = max(f[i + 1][j], f[i + 1][j + 1]) + a[i][j];
cout << f[1][1] << endl;
return 0;
}
最长上升子序列(LIS)
给定一个长度为 N 的数列，求数值严格单调递增的子序列的长度最长是多少。
输入格式
第一行包含整数 N。
第二行包含 N 个整数，表示完整序列。
输出格式
输出一个整数，表示最大长度。
数据范围
1≤N≤1000，
−10e9≤数列中的数≤10e9
输入样例：
7
3 1 2 1 8 5 6
输出样例：
4
分析
f[i] = max(f[j]) + 1，其中 \(j \in [0, i - 1]\)
由于子序列需要是严格单调递增，所以并不是[0,i - 1]中的所有位置都可以作为倒数第二个位置。必须满足a[j] < a[i]，才行。
时间复杂度\(O(n^2)\)
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1010;
int f[N], a[N];
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i], f[i] = 1;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= i - 1; j++)
if (a[j] < a[i]) f[i] = max(f[i], f[j] + 1);
int res = 0;
for (int i = 1; i <= n; i++) res = max(res, f[i]);
cout << res << endl;
return 0;
}
当数据范围扩大时，\(O(n^2)\)的时间复杂度已经不能满足要求时有一种纸牌游戏+二分的方法可以优化到\(O(nlogn)\)
首先，给你一排扑克牌，我们像遍历数组那样从左到右一张一张处理这些扑克牌，最终要把这些牌分成若干堆。
处理这些扑克牌要遵循以下规则：
- 只能把点数小的牌压到点数比它大的牌上；如果当前牌点数较大没有可以放置的堆，则新建一个堆，把这张牌放进去；如果当前牌有多个堆可供选择，则选择最左边的那一堆放置。
- 比如说上述的扑克牌最终会被分成这样 5 堆（我们认为纸牌 A 的牌面是最大的，纸牌 2 的牌面是最小的）。
按照上述规则执行，可以算出最长递增子序列，牌的堆数就是最长递增子序列的长度
每次处理一张扑克牌，需要找一个合适的牌堆放置，就可以使用二分来查找合适的牌堆
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 100010, INF = 1e9;
int heap[N], cnt;
int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) heap[i] = -INF;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
int l = 0, r = cnt;
while (l < r) {
int mid = l + r >> 1;
if (heap[mid] >= x) r = mid;
else l = mid + 1;
}
if (heap[l] >= x) heap[l] = x;
else heap[cnt++] = x;
}
cout << cnt << endl;
return 0;
}
最长公共子序列(LCS)
给定两个长度分别为 N 和 M 的字符串 A 和 B，求既是 A 的子序列又是 B 的子序列的字符串长度最长是多少。
输入格式
第一行包含两个整数 N 和 M。
第二行包含一个长度为 N 的字符串，表示字符串 A。
第三行包含一个长度为 M 的字符串，表示字符串 B。
字符串均由小写字母构成。
输出格式
输出一个整数，表示最大长度。
数据范围
1≤N,M≤1000
输入样例：
4 5
acbd
abedc
输出样例：
3
分析
其中00，可以直接用f[i - 1, j - 1] 表示，11可以直接用f[i - 1, j - 1] + 1来表示，但注意11需要满足a[i] = b[j]才行
对于01和10两种情况，是否能用f[i - 1, j]和f[i, j - 1] 表示呢？
f[i - 1, j] 表示的是由第一个序列的前i-1个字母和第二个序列的前j个字母构成的公共子序列，但是01这种情况是必须要包含b[j] 的，因此二者并不等价，01这种情况是包含在f[i - 1, j] 中的，即f[i - 1, j]表示的集合实际是要大于01这个集合的。但是01集合的最大值一定小于等于f[i - 1][j] 的最大值，好在f[i - 1][j]是包含在f[i][j]中的，因此用f[i - 1][j] 代表01集合是可以的，同理f[i][j - 1] 也可以代表10集合。虽然这几个集合是有重叠的，但是对于求max是无所谓的。
f[i - 1, j]和 f[i, j - 1]，实际是包含了00这个子集的，所以编写代码时，可以省略00这个子集。
#include<iostream>
using namespace std;
const int N = 1010;
char a[N], b[N];
int f[N][N];
int n, m;
int main() {
cin >> n >> m;
cin >> a + 1 >> b + 1;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) {
f[i][j] = max(f[i - 1][j], f[i][j - 1]);
if(a[i] == b[j]) f[i][j] = max(f[i][j], f[i - 1][j - 1] + 1);
}
cout << f[n][m] << endl;
return 0;
}
最短编辑距离
给定两个字符串 A 和 B，现在要将 A 经过若干操作变为 B，可进行的操作有：
- 删除–将字符串A中的某个字符删除。
- 插入–在字符串A的某个位置插入某个字符。
- 替换–将字符串A中的某个字符替换为另一个字符。
现在请你求出，将 A 变为 B 至少需要进行多少次操作。
输入格式
第一行包含整数 n，表示字符串 A 的长度。
第二行包含一个长度为 n 的字符串 A。
第三行包含整数 m，表示字符串 B 的长度。
第四行包含一个长度为 m 的字符串 B。
字符串中均只包含大小写字母。
输出格式
输出一个整数，表示最少操作次数。
数据范围
1≤n,m≤1000
输入样例：
10
AGTCTGACGC
11
AGTAAGTAGGC
输出样例：
4
分析
#include<iostream>
using namespace std;
const int N = 1010;
char a[N], b[N];
int f[N][N];
int main() {
int n, m;
cin >> n >> a + 1;
cin >> m >> b + 1;
for (int i = 0; i <= n; i++) f[i][0] = i;
for (int j = 0; j <= m; j++) f[0][j] = j;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) {
f[i][j] = min(f[i - 1][j] + 1, f[i][j - 1] + 1);
if (a[i] == b[j]) f[i][j] = min(f[i][j], f[i - 1][j - 1]);
else f[i][j] = min(f[i][j], f[i - 1][j - 1] + 1);
}
cout << f[n][m] << endl;
return 0;
}
区间DP
状态表示是某一个区间，比如f[i, j]表示的是[i ,j] 这个区间
石子合并
设有 N 堆石子排成一排，其编号为 1，2，3，…，N。
每堆石子有一定的质量，可以用一个整数来描述，现在要将这 N 堆石子合并成为一堆。
每次只能合并相邻的两堆，合并的代价为这两堆石子的质量之和，合并后与这两堆石子相邻的石子将和新堆相邻，合并时由于选择的顺序不同，合并的总代价也不相同。
例如有 4 堆石子分别为 1 3 5 2， 我们可以先合并 1、2堆，代价为 4，得到 4 5 2， 又合并 1，2 堆，代价为 9，得到 9 2 ，再合并得到 11，总代价为 4+9+11=24；
如果第二步是先合并 2，3 堆，则代价为 7，得到 4 7，最后一次合并代价为11，总代价为4+7+11=22。
问题是：找出一种合理的方法，使总的代价最小，输出最小代价。
输入格式
第一行一个数 N 表示石子的堆数 N。
第二行 N 个数，表示每堆石子的质量(均不超过 1000)。
输出格式
输出一个整数，表示最小代价。
数据范围
1≤N≤300
输入样例：
4
1 3 5 2
输出样例：
22
分析
f[i,j] = min(f[i,k] + f[k+1,j]) + sum[i,j]
其中 \(k \in [i,j-1]\) ，而其中的sum[i,j] 表示第i堆到第j堆的石子的总质量。因为最后一步的合并代价始终是sum[i,j]，这个可以用前缀和来处理。
时间复杂度：状态数量是二维，是\(n^2\)的，状态的计算，是枚举k，是 \(O(n)\)的计算量，所以一共的时间复杂度是 O ( n 3 ) \(O(n^3)\) 的。
区间DP，需要注意循环时的顺序，我们需要保证在计算f[i,j]时，需要的其他全部的f的值，都已经被算好了。所以这里我们按区间长度从小到大来枚举，先枚举区间长度为1，所有的f[i,j]，再枚举区间长度为2，…
所有区间DP类的问题，都可以用这种模式来做，先从小到大循环区间的长度（区间长度1，2，3，…），然后内层循环就循环区间的起点。
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 310;
int f[N][N], s[N];
int n;
int main() {
memset(f, 0x3f, sizeof f);
cin >> n;
for (int i = 1; i <= n; i++) cin >> s[i], s[i] += s[i - 1];
for (int i = 1; i <= n; i++) f[i][i] = 0;
for (int len = 2; len <= n; len++)
for (int i = 1; i + len - 1 <= n; i++) {
int l = i, r = i + len - 1;
for (int k = l; k < r; k++)
f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + s[r] - s[l - 1]);
}
cout << f[1][n] << endl;
return 0;
}
计数dp
前面几种DP，求的都是最值，而整数划分，求解的是方案数
整数划分
一个正整数 n 可以表示成若干个正整数之和，形如：n=n1+n2+…+nk，其中 n1≥n2≥…≥nk,k≥1。
我们将这样的一种表示称为正整数 n 的一种划分。
现在给定一个正整数 n，请你求出 n 共有多少种不同的划分方法。
输入格式
共一行，包含一个整数 n。
输出格式
共一行，包含一个整数，表示总划分数量。
由于答案可能很大，输出结果请对 10e9+7取模。
数据范围
1≤n≤1000
输入样例:
5
输出样例：
7
分析：
完全背包做法：按照完全背包的思路来想，有i属于1到n，共n种物品，每种物品体积为i，每种物品能使用无限次，背包的体积为n，问恰好能装满背包的物品选法的方案总数。
f[i][j] = f[i - 1][j] + f[i - 1][j - i] + f[i - 1][j - 2i] + .... + f[i - 1][j - k*i]
f[i][j - i] = f[i - 1][j - i] + f[i - 1][j - 2i] + .... + f[i - 1][j - k*i]
所以：
f[i][j] = f[i - 1][j] + f[i][j - i]
优化至一维
f[j] = f[j] + f[j - i]
#include <iostream>
using namespace std;
const int N = 1010, MOD = 1e9 + 7;
int f[N];
int main() {
int n;
cin >> n;
f[0] = 1;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (j >= i) f[j] = (f[j] + f[j - i]) % MOD;
cout << f[n] << endl;
return 0;
}
其他思路
用f[i][j]表示，所有总和是i，并且恰好表示成j个数的和的方案，f[i][j]的值是方案的数量。
集合划分，能够分为如下两类
- 方案中最小值是1的所有方案，这时候去掉一个1，此时和变成了
i - 1，个数变成了j - 1，即f[i - 1][j - 1] - 方案中最小值大于1的所有方案，此时将j个数都减去1，此时和变成了
i - j，个数还是j，即f[i - j][j]
最终答案，就是f[n][1] + f[n][2] + f[n][3] + … + f[n][n]
#include <iostream>
using namespace std;
const int N = 1010, MOD = 1e9 + 7;
int f[N][N];
int main() {
int n;
cin >> n;
f[0][0] = 1;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= i; j++)
f[i][j] = (f[i - 1][j - 1] + f[i - j][j]) % MOD;
int res = 0;
for (int i = 0; i <= n; i++) res = (res + f[n][i]) % MOD;
cout << res << endl;
return 0;
}