线性dp
即递推状态转移方程有明显的线性关系,可能是1维线性,可能是2维线性,等等
如数字三角形:https://www.acwing.com/problem/content/900/
首先考虑状态表示和状态计算
给图一个编号,如图,7为(4,2)
状态表示:
f[i][j]表示所有从起点,走到i,j的路径的集合
f[i][j]的值表示所有路径集合中值的最大值
状态计算:
即状态划分,分类
可以用所有从左上方来的点,和所有从右上方来的点
这一标准来划分集合,比如(4,2),就是由(3,1)和(3,2)得来的
这样计算也需要绕一下
可以考虑去除终点,即不考虑走到(4,2)这个点,那么所有路径的值都会减去7,但是最大的路径依然是那条路径,不会改变
那么就变成:
左上:所有从起点,走到(3,1)的路径的最大值
右上,所有从起点,走到(3,2)的路径的最大值
那么状态转移方程为:f[i][j]=max(f[i-1][j-1] , f[i-1][j] ) + a[i][j]
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 510;
const int INF = 1e8;
int n;
int f[N][N];
int a[N][N];
int res=-INF;
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++)//i+1防止越界
f[i][j]=-INF;//memset(f,-0x3f,sizeof f)
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],f[i-1][j])+a[i][j];
for(int j=1;j<=n;j++)res=max(res,f[n][j]);
cout << res << endl;
return 0;
}从上往下设置为负无穷的原因是： 由于f数组未初始化默认为0，且测试数据中路径中含负值。若不初始化为负无穷大，则访问到三角形外的区域时，会导致最长距离计算错误。所以要初始化负无穷。
当然这道题还可以从下往上分析
那么f[i][j]就是由左下和右下得来的,取一个max即可
即f[i][j]=max(f[i+1][j-1],f[i+1][j] ) + a[i][j]
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 510;
const int INF = 1e8;
int n;
int f[N][N];
int a[N][N];
int res=-INF;
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=1;j<=i;j++)
f[i][j]=max(f[i+1][j],f[i+1][j+1])+a[i][j];
cout << f[1][1] << endl;
return 0;
}如此,就不需要初始化为负无穷了,因为转移方程不会越界访问到三角形的外面区域
最长上升子序列:https://www.acwing.com/problem/content/897/
状态表示:f[i]表示所有以第i个数结尾的上子序列的集合
属性:f[i]的值表示所有以第i个数结尾的上升子序列的长度的最大值
那么可以枚举所有结尾,我们的答案就是在最后的f[1~n]中取一个max就行
状态计算--集合的划分:以倒数第2个数是哪个数来划分集合
如图,倒数第2个数可以是a[0],a[1],a[2]....a[i-1],即倒数第2个数可以有i种情况
每一种情况不一定存在,若存在a[2]>=a[i]那么a[2]是倒数第2个数的情况就不存在了
若存在,倒数第2个数<a[i],设它为a[j],有a[j]<a[i],那么这样的序列表示所有最后一个数是a[i],倒数第2个数是a[j]
这样的上升子序列的最大长度为所有以j为结尾的上升子序列长度,即f[j],再加上a[i]的1,即f[j]+1
即f[i]=f[j]+1,那么j可以是0~i-1,枚举后取max即可得到f[i],但是条件是a[j]<a[i]
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1010;
int n;
int a[N];
int f[N];
int res;
int main()
{
cin >> n;
for(int i=0;i<n;i++)cin >> a[i];
for(int i=0;i<n;i++)//枚举倒数第1个数
{
f[i]=1;//最极端情况,序列只有i一个数,因此最少为1
for(int j=0;j<=i-1;j++)//枚举倒数第2个数
{
if(a[j]<a[i])
f[i]=max(f[i],f[j]+1);
}
}
for(int i=0;i<n;i++)res=max(res,f[i]);
cout << res << endl;
return 0;
}这里有一个问题:如何把最长的序列保存下来?
可以用一个数组记录保存每一个状态是怎么转移过来的
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1010;
int n;
int a[N];
int f[N];
int g[N];
int res;
int main()
{
cin >> n;
for(int i=0;i<n;i++)cin >> a[i];
for(int i=0;i<n;i++)//枚举倒数第1个数
{
f[i]=1;//最极端情况,序列只有i一个数,因此最少为1
g[i]=0;
for(int j=0;j<=i-1;j++)//枚举倒数第2个数
{
if(a[j]<a[i])
if(f[i] < f[j]+1)
{
f[i]=f[j]+1;
g[i]=j;//f[i]是由f[j]转移过来的
}
}
}
int k = 0;
for(int i=0;i<n;i++)
if( f[k]<f[i])
k=i;
//此时f[k]为最大f[],表示以k结尾的所有上升序列选法最大值长度
for(int i=0,len=f[k];i<len;i++)
{
cout << a[k] << ' ';
k=g[k];//倒序还原,即f[k]是由f[g[k]]转移到的
}
cout << res << endl;
return 0;
}需要注意的是,这样的方案记录是倒序的
最长公共子序列:https://www.acwing.com/problem/content/899/
这里的状态表示和状态划分比较绕
状态表示:即所有在a序列中前i个字母中选,在b序列中前j个字母中选,这样的子序列的集合
属性:f[i][j]的值表示这样的所有序列的集合的最大长度
状态划分:
a[i],b[j]是否出现来划分集合(a序列中第i个字母和b序列中第j个字母是否出现),即00,01,10,11, 00表示a[i],b[j]都没出现0,1表示a[i]不出现,b[j]出现
这样f[i][j]就是这四个集合中取一个max即可
对于00:不选a[i]和b[j]这样的集合等价为所有第一个序列的前i-1个字母出现并且在第二个序列前j-1个字母中出现的子序列
即f[i-1][j-1]
对于11:即必定选了a[i]和b[j]这样的子序列(既然是公共子序列,那么此时a[i]=b[j]),可以先不考虑a[i]和b[j]的所有选法序列,那么就是f[i-1][j-1],它表示的是在前i-1,j-1个字母中选,这样的子序列的最大长度,那么要选上a[i]或者b[j]的话,也就是长度加个1
那么总长度就是f[i-1][j-1]+1
而对于01,10这样的选法更加绕
01,10表示的是必定不选a[i],必定选b[j] 和 必定选a[i]和必定不选b[j]
而我们的f[i][j]的定义是所有在a序列中前i个字母中选 ,在b序列中前j个字母中选
我们的定义集合不一定必须要包含a[i]和b[j],只是在1~i,1~j中选而已(可能包含a[i]或b[j])
这样就意味着f[i-1][j]包含着我们01情况,且f[i][j-1]包含着10的情况,他们是子集关系,并不等价
但是由于划分的集合是求序列长度的最大值,那么实际上我们可以用f[i-1][j]来替换01这样的集合的
即求f[i-1][j]这样的序列的长度的最大值,来替换求01的序列的长度的最大值
同理f[i][j-1]替换10集合
01的max<=f[i-1][j] 10的max<=f[i][j-1]
即求全局所有集合的MAX时,若干个集合是可以有交集的
而一般f[i-1][j-1]一般都不写,因为(根据定义)它一定包含在f[i-1][j]和f[i][j-1]中的
所以一般都是只写三个情况
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1010;
int f[N][N];
int n,m;
char a[N],b[N];
int main()
{
cin >> n >> m;
scanf("%s%s",a+1,b+1);//读到1~n,1~m,而不是0~n-1,因为转移方程有-1的话,需要从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])//11的情况
f[i][j]=max(f[i][j],f[i-1][j-1]+1);
}
cout << f[n][m] << endl;
}区间DP
区间dp的状态表示表示的是某一段区间
石子合并:https://www.acwing.com/problem/content/284/
状态表示:f[i][j]表示将第i堆到第j堆石子合并成一堆的所有合并方式
属性:所有合并方式的最小代价
那么根据定义,答案就是f[1][n]
状态计算-划分集合:以最后一次合并的分界线来分类,最后一次合并必定只有两堆石子,两堆石子有一个分界线
以最后一次分界线的位置来划分集合,一共有j-i+1类子集,把这些子集取一个min就是总共最小代价
设共有k堆石子,左边有多少堆石子就说明分界线在哪
那么就有左边只有一个,那么分界点就是左边的个数,1
假设分界线为k
左边为i,k 右边为k+1,j 将其合并
那么这样以k为分界线的集合去合并
可以先去除所有这一类的最后一步,再加上最后一步的代价
用定义来递归套一下,即f[i][k]+f[k+1][j]即两边分别的最小代价
再加上这两个堆合并的最小代价,即i~j的总重
可以用前缀和表示,即s[j]-s[i-1]
即f[i][k]+f[k+1][j]+s[j]-s[i-1]
那么f[i][j]=min(f[i][k]+f[k+1][j]+s[j]-s[i-1])
k从i枚举到j-1(分界线右边至少要有一堆,因此为j-1)
这里要注意枚举顺序
要保证算每一个f[i][j],它用到的状态都应该被算好了,所以要按照一定顺序保证符合这个条件
可以按照区间长度从小到大枚举
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 310;
int n;
int s[N];
int f[N][N];
int main()
{
cin >> n;
for(int i=1;i<=n;i++)cin >> s[i];
for(int i=1;i<=n;i++)s[i]+=s[i-1];
for(int len=2;len<=n;len++)//枚举区间长度
{
for(int i=1;i+len-1<=n;i++)//枚举左端点
{
int l=i,r=i+len-1;//分界点
f[l][r]=1e8;//初始化
for(int k=l;k<r;k++)
f[l][r]=min(f[l][r],f[l][k]+f[k+1][r]+s[r]-s[l-1]);
}
}
cout << f[1][n] << endl;
return 0;
}