线性DP问题
DP时间复杂度
时间复杂度等于状态数量乘以计算每一个状态所需要的时间
ACWING898数字三角形
思想
这是三角形在数组中的排列方式
注意边界问题，以及初始化要把数组值初始化成负无穷（因为数据有负数）
#include<bits/stdc++.h>
using namespace std;
const int RES = 1e9;
const int MAXN=1005;
int dp[MAXN][MAXN];
int a[MAXN][MAXN];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int i,j,n,ans=-RES;
cin>>n;
for(i=0;i<=n;i++)
for(j=0;j<=n;j++)
{
a[i][j]=-RES;
dp[i][j]=-RES;
}
for(i=1;i<=n;i++)
for(j=1;j<=i;j++)
{
cin>>a[i][j];
}
dp[1][1]=a[1][1];
for(i=2;i<=n;i++)
for(j=1;j<=i;j++)
{
dp[i][j]=max(dp[i-1][j-1]+a[i][j],dp[i-1][j]+a[i][j]);
}
for(j=1;j<=n;j++)
{
ans=max(dp[n][j],ans);
}
cout<<ans<<endl;
return 0;
}
ACWING895 最长上升子序列
给定一个长度为 N 的数列，求数值严格单调递增的子序列的长度最长是多少。
输入格式
第一行包含整数 N 。
第二行包含 N 个整数，表示完整序列。
输出格式
输出一个整数，表示最大长度。
数据范围
1≤N≤1000 ，
−109≤数列中的数≤109
输入样例：
7
3 1 2 1 8 5 6
输出样例：
4
思想
代码略
注意：如果想输出最长上升子序列，只需新开一个数组记录倒数第二个数的位置即可
ACWING897最长公共子序列
给定两个长度分别为 N 和 M 的字符串 A 和 B ，求既是 A 的子序列又是 B 的子序列的字符串长度最长是多少。
输入格式
第一行包含两个整数 N 和 M 。
第二行包含一个长度为 N 的字符串，表示字符串 A 。
第三行包含一个长度为 M 的字符串，表示字符串 B 。
字符串均由小写字母构成。
输出格式
输出一个整数，表示最大长度。
数据范围
1≤N,M≤1000
输入样例：
4 5
acbd
abedc
输出样例：
3
思想
求最大值，子问题可以重复，不漏掉就没问题（但求数量的，子问题不能重复）
比如A和B构成C，A和B有重复的地方
那么求集合C中的最大值，只需先求集合A的最大值，再求集合B的最大值，最后再把两个最大值比较，最后求出的最大值就是C的最大值
状态计算比较复杂，分为四种情况：
00：不包括i也不包括j
01：包括j但不包括i
10：包括i但不包括j
11：包括i也包括j
注意
1.f[i-1][j-1]已经在后三种情况中了，所以实际上只需考虑后三种情况
2.f[i-1][j]和f[i][j-1]和“只出现j，没出现i”“只出现i，没出现j”的概念是不同的，但因为前两者包括后两者，所以可以通过求前两者的最大值求出整体的最大值（上面ABC的例子）
代码：
#include <bits/stdc++.h>
using namespace std;
const int N=1010;
char a[N],b[N];
int f[N][N];
int main()
{
int n,m,i,j;
scanf("%d%d",&n,&m);
scanf("%s%s",a+1,b+1);
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
{
f[i][j]=max(f[i][j-1],f[i-1][j]);
if(a[i]==b[j])f[i][j]=max(f[i][j],f[i-1][j-1]+1);
}
printf("%d",f[n][m]);
return 0;
}
/*10 10
nqunjucfgh
irsfovvqah*/