线性dp
2021-02-20 本文已影响0人
Tsukinousag
数字三角形
原题链接
一直走到底层，要求找出一条路径，使路径上的数字的和最大。
#include <iostream>
#include <algorithm>
using namespace std;
const int N=510;
const int INF=1e9;
int n;
int a[N][N],dp[N][N];
int main()
{
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++)//处理在右边界溢出问题，右边界的旁边初始化为-∞
dp[i][j]=-INF;
dp[1][1]=a[1][1];//负无穷的时候必须初始化
for(int i=2;i<=n;i++)
for(int j=1;j<=i;j++)
dp[i][j]=max(dp[i-1][j-1]+a[i][j],dp[i-1][j]+a[i][j]);
int res=-INF;
for(int j=1;j<=n;j++)
res=max(res,dp[n][j]);
cout<<res<<endl;
return 0;
}
最长上升子序列Ⅰ（模板）（O（n²））
原题链接
给定一个长度为N的数列，求数值严格单调递增的子序列的长度最长是多少。
N=1000
#include<iostream>
using namespace std;
const int N=1010;
int a[N],dp[N];
int n;
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
for(int i=1;i<=n;i++)
{
dp[i]=1;//只有a[i]一个数
for(int j=1;j<i;j++)
if(a[j]<a[i])
dp[i]=max(dp[i],dp[j]+1);
}
int res=0;
for(int i=1;i<=n;i++)
res=max(res,dp[i]);
cout<<res;
return 0;
}
最长上升子序列Ⅱ(单调性优化+二分查找)（O（nlogn））
原题链接
N=100000
优化算法Ⅰ：
1.利用DP求取针对最末位的元素的最长的子序列，如果子序列的长度相同，那么最末位的元素较小的在之后会更优（因为末位更小更加有机会接新的序列）
因此重新定义集合：
具体步骤：初始化dp[i],每个设置为INF，从头往后插入一个a[j],比较大小，dp[i]=min(d[i],a[j])进行更新得到单调递增序列，因为递增序列，所以可以二分查找更新位置
#include <iostream>
#include <algorithm>
using namespace std;
const int N=1e5+10;
const int INF=0x3f3f3f3f;
int n;
int a[N],dp[N];
int main()
{
cin>>n;
fill(dp,dp+n,INF);
for(int i=0;i<n;i++)
cin>>a[i];
for(int i=0;i<n;i++)
*lower_bound(dp,dp+n,a[i])=a[i];//注意lower_bound返回的是指针，在返回处直接赋值a[i]
printf("%d\n",lower_bound(dp,dp+n,INF)-dp);//第一个无穷处-0处=长度
return 0;
}
0 1 2 3 4 5
1 2 2 2 3 4
4-1=3
实操心得：长度为n的有序数组a中的k的个数
upper_bound(a,a+n,k)-lower_bound(a,a+n,k)=3，长度是3
*upper_bound(a,a+n,k)=3,返回了4处的值
最长公共子序列 (O（nm）)
原题链接
#include <iostream>
#include <algorithm>
using namespace std;
const int N=1010;
int n,m;
char a[N],b[N];
int dp[N][N];
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=m;i++) cin>>b[i];
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(a[i]==b[j])
dp[i][j]=dp[i-1][j-1]+1;
else
dp[i][j]=max(dp[i][j-1],dp[i-1][j]);
}
}
cout<<dp[n][m]<<endl;
return 0;
}
最短编辑距离
原题链接
给定两个字符串A和B，现在要将A经过若干操作变为B，可进行的操作有：
删除–将字符串A中的某个字符删除。
插入–在字符串A的某个位置插入某个字符。
替换–将字符串A中的某个字符替换为另一个字符。
现在请你求出，将A变为B至少需要进行多少次操作。
#include <iostream>
#include <algorithm>
using namespace std;
const int N=1010;
int n,m;
int dp[N][N];
char a[N],b[N];
int main()
{
scanf("%d%s",&n,a+1);
scanf("%d%s",&m,b+1);
for(int i=0;i<=n;i++) dp[i][0]=i;//b无，删i次a
for(int i=0;i<=m;i++) dp[0][i]=i;//a无，增i次a
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
dp[i][j]=min(dp[i-1][j]+1,dp[i][j-1]+1);//1 2 操作
//特判 第三种情况
if(a[i]==b[j])
dp[i][j]=min(dp[i][j],dp[i-1][j-1]);
else
dp[i][j]=min(dp[i][j],dp[i-1][j-1]+1);
}
}
cout<<dp[n][m]<<endl;
return 0;
}
编辑距离
原题链接
#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;
const int M=11,N=1010;
int n,m;
char str[N][M];
int dp[M][M];
int solve(char a[],char b[])
{
int lena=strlen(a+1);//此处是strlen(a+1) scanf("%s",a+1); printf("%d",strlen(a));输出是0
int lenb=strlen(b+1);
for(int i=0;i<=lena;i++) dp[i][0]=i;
for(int j=0;j<=lenb;j++) dp[0][j]=j;
for(int i=1;i<=lena;i++)
{
for(int j=1;j<=lenb;j++)
{
dp[i][j]=min(dp[i][j-1]+1,dp[i-1][j]+1);
if(a[i]==b[j])
dp[i][j]=min(dp[i][j],dp[i-1][j-1]);
else
dp[i][j]=min(dp[i][j],dp[i-1][j-1]+1);
}
}
return dp[lena][lenb];
}
int main()
{
cin>>n>>m;
for(int i=0;i<n;i++) scanf("%s",str[i]+1);
while(m--)
{
char s[N];
int t;
scanf("%s%d",s+1,&t);
int res=0;
for(int i=0;i<n;i++)
if(solve(str[i],s)<=t) res++;
cout<<res<<endl;
}
return 0;
}
实操心得：
int lena=strlen(a+1)此处是strlen(a+1)
scanf("%s",a+1);
printf("%d",strlen(a));输出是0
