动态规划之常⽤dp类型
⽂章⽬录
常⽤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
cstring转为int输出样例
30
分析
状态表⽰f(i,j)：所有从起点⾛到(i,j)的路径
属性:Max
状态计算:f(i,j) -- [来⾃左上|来⾃右上]
左上:f(i-1,j-1)+a(i,j)
右上:f(i-1,j)+a(i,j)
状态转移⽅程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 =0x3f3f3f;
int n;
int v[N][N], f[N][N];
int main()
{
cin >> n;
for(int i =1; i <= n; i ++)
for(int j =1; j <= i; j ++)
cin >> v[i][j];
for(int i =0; i <= n +1; i ++)//初始化的时候需要多初始化⼀些
for(int j =0; j <= n +1; j ++)
f[i][j]=-INF;
f[1][1]= v[1][1];//第⼀⾏第⼀列的值 = v[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])+ v[i][j];
int res =-INF;
for(int i =1; i <= n; i ++)
res =max(res, f[n][i]);
cout << res << endl;
return0;
}
最长上升⼦序列
题⽬描述
给定⼀个长度为 N 的数列，求数值严格单调递增的⼦序列的长度最长是多少。输⼊格式
第⼀⾏包含整数 N。
第⼆⾏包含 N 个整数，表⽰完整序列。
输出格式
输出⼀个整数，表⽰最⼤长度。
数据范围
1≤N≤1000，
−109≤数列中的数≤109
输⼊样例
7
3 1 2 1 8 5 6
输出样例
4
分析
状态表⽰f[i]：所有以第i个数结尾的上升⼦序列集合
属性: Max
状态计算f[i] -- [0|1|2|3|……|i-1]
aj < ai: f[j]+1
状态转移f[i] = max(f[j]+1),j = 0,1,2,……,i-1
核⼼代码O(N^2)
#include<iostream>
#include<algorithm>
using namespace std;
const int N =1010, INF =0x3f3f3f3f;
int n;
int a[N],f[N];
int main()
{
cin >> n;
for(int i =1; i <= n; i ++) cin >> a[i];
for(int i =1; i <= n; i ++){
f[i]=1;
for(int j =0; j <= i -1; j ++)
if(a[i]> a[j]){
f[i]=max(f[i], f[j]+1);
}
}
int res =-INF;
for(int i =1; i <= n; i ++)
res =max(res, f[i]);
cout << res << endl;
return0;
}
优化
思路
将所有长度的最长上升⼦序列的最⼩值存在下，
猜想：随着最长上升⼦序列长度的增加，数值应该严格单调递增
增加⼀个数到数列中，到⼀个数使之前⼀个数≤ai＜后⼀个数，接着⽤ai覆盖右边的数。代码
#include<iostream>
using namespace std;
const int N =100010;
int n;
int a[N], q[N];
int main()
{
cin >> n;
for(int i =0; i < n; i ++) cin >> a[i];
int len =0;
q[0]=-2e9;
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];
}
cout << len << endl;
return0;
}
最长公共⼦序列
题⽬描述
给定两个长度分别为 N 和 M 的字符串 A 和 B，求既是 A 的⼦序列⼜是 B 的⼦序列的字符串长度最长是多少。输⼊格式
第⼀⾏包含两个整数 N 和 M。
第⼆⾏包含⼀个长度为 N 的字符串，表⽰字符串 A。
第三⾏包含⼀个长度为 M 的字符串，表⽰字符串 B。
字符串均由⼩写字母构成。
输出格式
输出⼀个整数，表⽰最⼤长度。
数据范围
1≤N,M≤1000
输出样例
4 5
acbd
abedc
输出样例
3
题⽬分析
状态表⽰f(i,j)：所有在第⼀个序列的前i个字母中出现，且在第⼆个序列的前j个字母中出现的⼦序列属性:Max
状态计算f(i,j) -- [00|01|10|11]
00：不选ai、bj  --  f[i-1,j-1]
01：不选ai、选bj  ∈  f[i-1,j]
10：选ai、不选bj  ∈  f[i,j-1]
11：选ai、bj  --  f[i-1,j-1] + 1
其中f[i-1,j-1]  ∈  [ f[i-1,j] | f[i,j-1] ]
代码
#include<iostream>
#include<algorithm>
using namespace std;
const int N =1010;
char a[N], b[N];
int f[N][N];
int n, m;
int main()
{
cin >> n >> m;
scanf("%s%s",a +1, b +1);
for(int i =1; i <= n; i ++)
for(int j =0; j <= m; j ++){
f[i][j]=max(f[i -1][j], f[i][j -1]);
f[i][j]=max(f[i][j], f[i -1][j -1]+(a[i]== b[j]));
}
cout << f[n][m]<< endl;
return0;
}
最短编辑距离
题⽬描述
给定两个字符串 A 和 B，现在要将 A 经过若⼲操作变为 ，可进⾏的操作有：
1. 删除–将字符串 A 中的某个字符删除。
2. 插⼊–在字符串 A 的某个位置插⼊某个字符。
3. 替换–将字符串 A 中的某个字符替换为另⼀个字符。
现在请你求出，将 A 变为 B ⾄少需要进⾏多少次操作。
输⼊格式
第⼀⾏包含整数 n，表⽰字符串 A 的长度。
第⼆⾏包含⼀个长度为 n 的字符串 A。
第三⾏包含整数 m，表⽰字符串 B 的长度。
第四⾏包含⼀个长度为 m 的字符串 B。
字符串中均只包含⼤写字母。
输出格式
输出⼀个整数，表⽰最少操作次数。