[动态规划](2)线性DP
数字三角形
引言:
所谓线性DP，是咱们的递推方程，有一个明显的线性关系,他可能是一维线性，也可能是二维线性的
思维导图:
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
转换为：
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
代码：
//取所有能走到f[i][j]路径的最大值,依照题意,f[i][j]状态可由其左上和右上转移过来
//左上既是f[i-1][j-1],右上既是f[i-1][j]
//既可得出状态转移方程为:f[i][j]=max(f[i-1][j-1]+a[i][j],f[i-1][j]+a[i][j])
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;
const int N = 1010;//数据范围
const int INF = 0x3f3f3f3f;//极小值
int n;//数字三角形层数
int a[N][N], f[N][N];//a数组存储数字三角形,f数组存储状态转移
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= i; j++)
scanf("%d", &a[i][j]);
//初始化状态转移数组,由于每行最后一个数可以由其右上转移过来,所以需要初始化边界+1
for (int i = 1; i <= n; i++)//行不用
for (int j = 0; j <= i + 1; j++)//对照数字三角形图即可理解
f[i][j] = -INF;
//进行状态转移
for (int i = 1; i <= n; i++)
for (int j = 1; j <= i; j++)
f[i][j] = max(f[i - 1][j - 1] + a[i][j], f[i - 1][j] + a[i][j]);
int res = -INF;
for (int i = 1; i <= n; i++) res = max(f[n][i], res);
cout << res << endl;
return 0;
}最长上升子序列
思维导图:
代码
//n²的时间复杂度，在所有上升子序列中选取最长的序列长度
//则可以定义所有以 a[i] 结尾的 子序列 中 最长的上升子序列
//若在a[i]之前出现元素a[j]比a[i]小,则a[j]+1与a[i]作比较
#include<iostream>
using namespace std;
const int N = 1010;
int a[N],f[N];
int n;
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=1;i<=n;i++){
f[i]=1;//全部初始化为1,代表以自身结尾,只包含自身一个元素
for(int j=1;j<=i;j++)
if(a[j]<a[i]) //若出现a[j]<a[i],则可添加a[j]所在子序列长度加上a[i],与当前以i结尾最长子序列长度选取max
f[i] = max(f[i],f[j]+1);
}
int res=-0x3f3f3f3f;
for(int i=1;i<=n;i++) res=max(res,f[i]);
cout<<res<<endl;
return 0;
}
二分优化
模板题:896. 最长上升子序列 II - AcWing题库
思路:
- 基于 朴素算法 的单调性:找到一个最大的小于等于当前数的数,我们可以用 二分 来优化，我们利用二分找到最后一个小于它的数 j，然后去判断以 j 结尾的子序列长度 + 1 是否大于 i
代码:
#include<iostream>
using namespace std;
const int N =100010;
int a[N],f[N];
int n;
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
f[0]=-0x3f3f3f3f;//长度为0的数是0x3f,作为哨兵
int len=0;//最大长度
for(int i=1;i<=n;i++){
int l=0,r=len;
while(l<r){//利用二分去在当前长度区间找寻最后一个小于它的数
int mid = l+r+1>>1;
if(f[mid] >= a[i]) r=mid-1;
else l=mid;
}
len=max(len,r+1);
f[r+1]=a[i];//更新当前长度的结尾数字
}
cout<<len<<endl;
return 0;
}
/*
q[r + 1] = a[i];这里并没有选择最小的是因为可以保证“相等长度的上升序列，
后来得到的序列的结尾数值一定小于或等于前面得到的”，假设先前得到的序列xxxa，
后来得到的序列xxxb，a和b满足b在a的后面且b>a，
那么显然xxxb一定不是以b结尾的最长上升子序列，正确序列中一定包含a，
所以假设不成立，命题得证。
*/最长公共子序列
思维导图:
代码
//状态表示:所有在第一个序列的前i个字母中出现.且在第二个序列的前j个字母中出现的最大值
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1010;
int n,m;
char a[N],b[N];
int f[N][N];
int main(){
scanf("%d %d",&n,&m);
cin>>a>>b;
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]);
//选a的第i个字母和选b的第j个字母的最大值
if(a[i-1]==b[j-1])
f[i][j] = max(f[i][j],f[i-1][j-1]+1);
//当两个字母相等时,选取这个字母与不选这个字母的最大值
}
}
cout<<f[n][m]<<endl;
return 0;
}最短编辑距离
思维导图：
代码:
//状态表示:所有将a[1 - i]变换到b[1 - j]的最小值
#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 >> a;
cin >> m >> b;
for (int i = 0; i <= m; i++) f[0][i] = i;//将a的前0个字母变换到b[1-m]个字母,只有增一种操作
for (int i = 0; i <= n; i++) f[i][0] = i;//将a[1 - n]个字母变换到b的前0个字母,只有删一种操作
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);
//当a的前i-1个字母与b的前j个字母相等时,“增” 一种操作
//当a的前i个字母与b的前j-1个字母相等时,“删” 一种操作
if (a[i - 1] == b[j - 1]) f[i][j] = min(f[i][j], f[i - 1][j - 1]); //当a的第i个字母与b的第j个字母相等时,不需要操作
else f[i][j] = min(f[i][j], f[i - 1][j - 1] + 1);//当a的第i个字母与b的第j个字母不相等时,进行 “改” 操作
}
cout << f[n][m] << endl;
return 0;
}