二、线性DP
线性DP：递推方式为线性的递推式。
1、数字三角形
题目链接： 898. 数字三角形
1.1题目描述
给定一个如下图所示的数字三角形，从 顶部 出发，在每一结点可以选择移动至其左下方的结点或移动至其右下方的结点， 一直走到底层 ，要求找出一条路径，使 路径上的数字的和最大。
7 3 8 8 1 0 2 7 4 4 4 5 2 6 5
输入格式
第一行包含整数 n，表示数字三角形的层数。
接下来 n 行，每行包含若干整数，其中第 i 行表示数字三角形第 i 层包含的整数。
输出格式
输出一个整数，表示最大的路径数字和。
数据范围
1≤n≤500
−10000≤三角形中的整数≤10000
输入样例：
5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5
输出样例：
30
1.2思路分析
注：
DP问题下标从0开始还是从1开始
如果递推式中存在f[i-1]，即下标存在i-1,下标 从1开始，将f[0]设为了边界值。
否则，下标 从0开始，防止数组下标越界。
动态规划问题时间复杂度的计算
时间复杂度 = 状态数 * 转移的计算量
1）状态表示
注：如图，从 上到下 定义每 行，从 左上到右下 定义每 列
集合：所有从起点走到(i,j)的路径。
属性：f[i][j]表示满足条件集合中的最大路径的数字和。
2）状态计算
集合划分：从左上走到(i,j)和从右上走到(i,j)。
计算：①左上：先走到左上(i-1,j-1),最大路径的数字和为f[i-1][j-1]，然后再加上(i,j)点的数字，即f[i-1][j-1]+a[i][j]；②右上：先走到右上(i-1,j),最大路径的数字和为f[i-1][j]，然后再加上(i,j)点的数字，即f[i-1][j]+a[i][j]。将两种条件综合可得，f[i][j]=max(f[i-1][j-1]+a[i][j],f[i-1][j]+a[i][j])。
1.3代码实现
#include <iostream> using namespace std; const int N=510,INF=1e9; int n; int a[N][N]; int f[N][N]; int main() { cin>>n; for(int i=1;i<=n;i++){ for(int j=1;j<=i;j++){ cin>>a[i][j]; } } /*注意：不能初始化f数组全为0,因为a数组中存在负数，所以f数组也有可能是负数 若初始化全为0，就会将f数组中的负数给忽略掉，换句话说，若都初始化为0，说明 所有点一开始都存在最大值，我们需要使所有点一开始都不存在最大值，即初始化 全为负无穷，而对于下面边界处理时，如果该点的左上或者右上不存在时，仍然按 递推式计算后的值一定是负的，一定小于从存在的上方的点转移过来的最大值，所以 从不存在的那个点转移过来的就直接被max函数所比下去了，后续处理也比较方便。 */ for(int i=1;i<=n;i++){ /*对于每行的边界，需要用到的左上和右上的数， 个别数超出了a数组初始化的范围，所以要在f数组中每 行多初始化两个数，最前和最末两个数*/ for(int j=0;j<=i+1;j++){ f[i][j]=-INF; } } f[1][1]=a[1][1]; int res=-INF; 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]); } } for(int i=1;i<=n;i++){ res=max(f[n][i],res); } cout<<res; return 0; }
2、最长上升子序列
题目链接：895. 最长上升子序列
2.1题目描述
给定一个 长度为 N 的数列，求 数值严格 单调递增的子序列 的 长度最长 是多少。
输入格式
第一行包含整数 N。
第二行包含 N 个整数，表示完整序列。
输出格式
输出一个整数，表示最大长度。
数据范围
1≤N≤1000，
−109≤数列中的数≤109
输入样例：
7 3 1 2 1 8 5 6
输出样例：
4
2.2思路分析
注：状态转移，从 一维 开始来判断能否表示，依次上升维度。
1）状态表示
集合：所有以第i个数结尾的上升子序列。
属性：f[i]表示满足条件集合中的最长序列长度。
2）状态计算
集合划分：以第i个数前一位数是原序列的第几个元素划分集合。
计算：针对每一种状态，f[j]表示除第i个数后上升子序列的长度，即以第j个数结尾的上升子序列的最大长度。所以再加上第i个数的长度，即加上1，代表以第i个数结尾的最长上升子序列的长度，即f[j]+1。所以可得 f[i]=max(f[j]+1)（j为不超过i-1的数）。
2.3代码实现
#include <iostream> 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++){ //初始化：只有a[i]一个数，子序列长度为1 f[i]=1; //子序列中的数大于1，依次枚举第i个数前面的数 for(int j=1;j<i;j++){ //如果第j个数可以作为i的前一个数，才满足条件，进行递推 if(a[j]<a[i]){ f[i]=max(f[i],f[j]+1); } } } int ans=0; //找出最长上升子序列的长度 for(int i=1;i<=n;i++){ ans=max(f[i],ans); } cout<<ans; return 0; }
如何记录最长上升序列各元素为多少，并输出？
//如何记录最长上升子序列并且输出
//方法如下：
#include <iostream> using namespace std; const int N=1010; int n; int a[N],f[N],g[N];//利用g数组来记录序列中最后一位的前一位数字 //利用g数组从而可以来记录出最长序列的序列具体为哪几个数 int main(){ cin>>n; for(int i=1;i<=n;i++){ cin>>a[i]; } for(int i=1;i<=n;i++){ f[i]=1; g[i]=0; for(int j=1;j<i;j++){ if(a[j]<a[i]){ if(f[i]<f[j]+1){ f[i]=f[j]+1; g[i]=j; //用g数组记录i的前一位数字为第几个元素 } } } } int k=1;//用k记录以第几个数字结尾 for(int i=1;i<=n;i++){ //找出最长序列是以第几个数字结尾 if(f[k]<f[i]) k=i; } cout<<f[k]<<endl; //从大到小来输出最长上升子序列具体为多少 for(int i=0,len=f[k];i<len;i++){ cout<<a[k]<<" "; k=g[k]; } return 0; }
3、最长公共子序列
题目链接：897. 最长公共子序列
3.1题目描述
给定两个长度分别为 N 和 M 的字符串 A 和 B ，求 既是 A 的子序列又是 B 的子序列 的 字符串长度最长 是多少。
输入格式
第一行包含两个整数 N 和 M 。
第二行包含一个长度为 N 的字符串，表示字符串 A 。
第三行包含一个长度为 M 的字符串，表示字符串 B 。
字符串均由小写字母构成。
输出格式
输出一个整数，表示最大长度。
数据范围
1≤N,M≤1000
输入样例：
4 5 acbd abedc
输出样例：
3
3.2思路分析
1）状态表示
集合：所有在第一个序列的前i个字母中出现，而且在第二个序列的前j个字母中出现的子序列。
属性：f[i][j]表示满足条件集合中的最长子序列（字符串）长度。
2）状态计算
集合划分：以满足集合条件的集合中是否包含第一个序列的第i个字 a[i] 和第二个序列的第j个字母 b[j] 来划分集合，总共分为四类：不包含a[i]且不包含b[j]、不包含a[i]且包含b[j]、包含a[i]且不包含b[j]、包含a[i]且包含b[j]。
计算：针对每一种状态
1.f[i-1][j-1]。（该状态可省，因为后一种情况涵盖了它）根据集合定义可得。 2.f[i-1][j]。因为f[i-1][j]包含了第二个序列中第j个字母存在和不存在两种情况，所以范围比较大，与其他情况有重叠，但是对于求f[i][j]的最大值无影响。 3.f[i][j-1]。因为f[i][j-1]包含了第一个序列中第i个字母存在和不存在两种情况，所以范围比较大，与其他情况有重叠，但是对于求f[i][j]的最大值无影响。 4.f[i-1][j-1]+1。因为该情况中每一项都包含第一个序列的第i个字母（或者说是第二个序列的第j个字母），所以长度先都减去1，就是转化为第一种情况，最后再加上去掉字母的长度1，即可得到最大长度。
综上，f[i][j]=max(f[i-1][j],f[i][j-1],f[i-1][j-1]+1)。
3.3代码实现
string实现
#include <iostream> #include <string> using namespace std; const int N=1010; int n,m; string a="1",b="1"; int f[N][N]; int main(){ cin>>n>>m; string temp; cin>>temp; a+=temp; cin>>temp; b+=temp; 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]; return 0; }
char实现
#include <iostream> 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]); //第三种情况只有第一个序列第i个字母和第二个序列第j个字母相同，才存在 if(a[i]==b[j]){ f[i][j]=max(f[i][j],f[i-1][j-1]+1); } } } cout<<f[n][m]; return 0; }
三、区间DP
石子合并
题目链接：282. 石子合并
1.1题目描述
设有 N 堆石子排成一排，其编号为1,2,3,…,N。每堆石子有一定的质量，可以用一个整数来描述，现在要将这 N 堆石子合并成为一堆。
每次只能合并相邻的两堆，合并的代价为这两堆石子的质量之和，合并后与这两堆石子相邻的石子将和新堆相邻，合并时由于选择的顺序不同，合并的总代价也不相同。
例如有 4 堆石子分别为 1 3 5 2，我们可以先合并 1、2 堆，代价为 4，得到 4 5 2，又合并 1、2 堆，代价为 9，得到 9 2 ，再合并得到 11，总代价为 4+9+11=24；
如果第二步是先合并 2、3 堆，则代价为 7，得到 4 7，最后一次合并代价为 11，总代价为 4+7+11=22。
问题是：找出一种合理的方法，使总的代价最小，输出 最小代价。
输入格式
第一行一个数 N 表示石子的堆数 N。
第二行 N 个数，表示每堆石子的质量(均不超过 1000)。
输出格式
输出一个整数，表示最小代价。
数据范围
1≤N≤300
输入样例：
4 1 3 5 2
输出样例：
22
1.2思路分析
1）状态表示
集合：所有将第i堆石子到第j堆石子合并成一堆的合并方式。
属性：f[i][j]表示满足条件集合中的合并的最小代价。
2）状态计算
集合划分：以最后一次合并时的区间位置来划分，如图。
计算：针对每一种状态。合并的最小代价为，合并区间左边的最小代价+合并区间右边的最小代价+最后一次合并（合并整个区间的代价），即 f[i][j]=min(f[i][k]+f[k+1][j]+s[j]-s[i-1])。(s[j]-s[i-1]利用前缀和来计算合并整个区间的代价)
1.3代码实现
#include <iostream> 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]; return 0; }
