线性DP
[eg.1] 数字三角形:https://www.acwing.com/problem/content/900/
1.状态表示:
(1)集合:所有从起点走到(i,j)的路径
(2)属性:Max,即所有路径上的数值之和的最大值
2.状态计算:(对应集合的划分方式)
(1)到达当前点的路径来自于左上方:
f[i][j]=f[i-1][j-1]+a[i][j]
(2)到达当前点的路径来自于右上方:
f[i][j]=f[i-1][j]+a[i][j]
注意:边界的值会利用到三角形之外的值来计算,所以一开始需要把边界周围全部初始化为负无穷
代码如下:
#include<iostream>
#include<algorithm>
using namespace std;
const int N=510,INF=1e9;
int n;
int f[N][N];//表示从起点到fij的所有路径的最大值
int a[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++)
f[i][j]=-INF;
f[1][1]=a[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]+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;
}
或者直接从底向上来进行状态计算,由于终点是唯一的就不再需要枚举最后一行,甚至不需要进行初始化,上一行的每一个值都可以由下一行的值推出。(包括边界)
代码如下:
#include<iostream>
#include<algorithm>
using namespace std;
const int N=510,INF=1e9;
int n;
int f[N][N];//表示从起点到fij的所有路径的最大值
int a[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=n;i>=1;i--)
for(int j=n;j>=1;j--)
f[i][j]=max(f[i+1][j]+a[i][j],f[i+1][j+1]+a[i][j]);
cout<<f[1][1]<<endl;
return 0;
}
[eg.2] 最长上升子序列:https://www.acwing.com/problem/content/897/
1.状态表示:
(1)集合:f[i],以第i个数结尾的所有上升子序列
(2)属性:Max,即所有上升子序列的长度的最大值
2.状态计算
状态计算对应着集合的划分,这也是动态规划最难的地方TAT
在这里,由于子序列已经确定由原序列的第i位结尾,所以利用第i位数字前面的数字来将集合划分。
讨论第i位数前面的数确定的子序列,可以是:0(当前子序列只有第i位数) , 1(以第1位数结尾的子序列),2(以第2位数结尾的子序列)……
于是枚举,可以得到下面的代码
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1010;
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=1;j<i;j++){
if(a[j]<a[i])
f[i]=max(f[i],f[j]+1);
}
}
int res=0;
for(int i=1;i<=n;i++){
res=max(res,f[i]);
}
cout<<res<<endl;
return 0;
}
[eg.3] 最长公共子序列:https://www.acwing.com/problem/content/899/
注意,子序列和子串是不同的,子序列可以是离散的
1.状态表示:
(1)集合:f[i][j],所有在第一个序列的前i个字母中出现,并且在第二个序列的前j个字母中出现的子序列。
(2)属性:Max,即所有公共子序列长度中的最大值
2.状态计算:
f[i][j]的划分,一共四种情况:
若两个串分别为a,b,即对于a[i],b[j]有选或不选的情况,组合起来一共四种:00,01,10,11
00即都不选,则:f[i][j]=f[i-1][j-1]
01即选b[j],f[i][j]=f[i-1][j]
10即选a[i],f[i][j]=f[i][j-1]
11即都选,f[i][j]=f[i-1][j-1]+1
这里需要注意的是,01和10这两种情况涉及到的含义,f[i][j-1]表示所有出现在a串前i个字母并且出现在b串所有前j-1个字母中的子序列,并不一定选了a[i],但是一定包含选中a[i]的所有情况
换种说法,f[i-1][j]其实是00和01的并集,为什么呢?f[i-1][j]所代表的意思是不选a[i],但是可选可不选b[j],而选和不选正好是01和00。f[i][j-1]也是同样的道理,可选可不选a[i],但是max的计算不用担心重复 ,所以最终分为三类即可:
00+01:f[i][j]=f[i-1][j]
10:f[i][j]=f[i][j-1]
11:f[i][j]=f[i-1][j-1]+1
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
const int N=1010;
int n,m;
char a[N],b[N];
int f[N][N];
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++){
f[i][j]=max(f[i-1][j],f[i][j-1]);
if(a[i]==b[j]) f[i][j]=max(f[i][j],f[i-1][j-1]+1);
}
}
cout<<f[n][m]<<endl;
return 0;
}