线性DP
895. 最长上升子序列
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
for(int i=1;i<=n;i++)
{
dp[i]=1;//包含自己
for(int j=1;j<i;j++)
if(a[j]<a[i])
dp[i]=max(dp[j]+1,dp[i]);//是自己原本的子序列长还是新找到以a[j]结尾的子序列长
}
int re=-1e9;
for(int i=1;i<=n;i++)
re=max(re,dp[i]);
cout<<re;
return 0;
}
896. 最长上升子序列 II
int a[N],q[N];//q[i]表示长度为i的不同子序列末尾值的最小值
//整体思想及步骤:遍历a[i],把a[i]替换到q数组中小于等于a[i]的最大的一个q[k]的后面q[k+1]
int main()
{
cin>>n;
for(int i=0;i<n;i++)//输入从0开始,因为要二分
cin>>a[i];
for(int i=0;i<n;i++)
{
int l=0,r=len;//len是q数组的长度,也是最后的结果
while(l<r)
{
int mid=(l+r+1)/2;
if(q[mid]<a[i])
l=mid;
else
r=mid-1;
}
q[r+1]=a[i];
len=max(len,r+1);
}
cout<<len;
return 0;
}
897. 最长公共子序列
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1010;
int n,m;
char a[N],b[N];
int dp[N][N];//dp[i][j]表示a[1~i]与b[1~j]的最长公共子序列
//整体思路:判断a[i]与b[j]相不相等觉得dp[i][j]是等于dp[i-1][j-1]+1还是max(dp[i-1][j],dp[i][j-1])
int main()
{
cin>>n>>m;
scanf("%s%s",a+1,b+1);
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-1][j],dp[i][j-1]);
}
}
cout<<dp[n][m];
return 0;
}
902. 最短编辑距离
#include<iostream>
using namespace std;
const int N=1010;
int n,m,dp[N][N];
char a[N],b[N];
//整体思想:先对dp的两条边界进行初始化,然后对a[i]与b[j]的关系判断需要进行删除、增加还是更改操作
int main()
{
scanf("%d%s",&n,a+1);
scanf("%d%s",&m,b+1);
//初始化dp的两条边界
for(int i=0;i<=n;i++)
dp[i][0]=i;//将a[1~i]变成b[0],需要删掉a的i个字母,即需要i次操作
for(int i=0;i<=m;i++)
dp[0][i]=i;//将a[0]变成b[1~j],需要向a插入i个字母,即需要i次操作
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);
//dp[i-1][j]表示的是:删掉a[i],那么也就说明a[1~i-1]与a[1~j]是匹配的
//dp[i][j-1]表示的是:增加a[i],那么也就说明a[1~i]与a[1~j-1]是匹配的
if(a[i]==b[j])//如果a[i]与b[j]是相等的,那么不再需要替换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];
return 0;
}
区间DP
282. 石子合并
#include<iostream>
using namespace std;
const int N=310;
int n,sum[N];
int dp[N][N];//dp[i][j]表示将第i堆石子到第j堆石子合并的最小代价
/*
整体思路:得到最小代价的最后一步一定是 将左边石子和右边石子合并成一堆
那么最小代价是左边石子的最小代价dp[][]+右边石子的最小代价dp[][]+合并这两堆石子的代价
区间dp的模板:
一般先枚举区间长度(长度是1还是2因题而异),然后第二层循环枚举该区间的左端点,这时候就可以通过区间
和区间的左端点确定该区间,第三次循环枚举将该区间划分为两个区间的分界线k
*/
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
scanf("%d",&sum[i]);
for(int i=1;i<=n;i++)
sum[i]=sum[i-1]+sum[i];
for(int len=2;len<=n;len++)//枚举区间长度,区间长度必须从2开始,因为一定有两堆石子合并才存在最小代价
{
for(int j=1;j+len-1<=n;j++)//枚举区间左端点,j+len-1<=n是因为至少留一个点作右端点
{
int l=j,r=j+len-1;
dp[l][r]=1e9;
for(int k=l;k<r;k++)//枚举区间划分线k,这跟线切到的元素属于这个区间划分后的左边
{
dp[l][r]=min(dp[l][r],dp[l][k]+dp[k+1][r]+sum[r]-sum[l-1]);
//f[l][r]通过对不同划分求min得到该区间的最小代价
}
}
}
cout<<dp[1][n];
return 0;
}