前言
往期系列文章
动态规划之01背包
动态规划之完全背包
线性动态规划，是较常见的一类动态规划问题，其是在线性结构上进行状态转移，这类问题不像背包问题、区间DP等有固定的模板。
线性动态规划的目标函数为特定变量的线性函数，约束是这些变量的线性不等式或等式，目的是求目标函数的最大值或最小值。
下面 我来详细讲解 线性DP 的几个常见模型
线性DP
数字三角形模型
给定一个如下图所示的数字三角形，从顶部出发，在每一结点可以选择移动至其左下方的结点或移动至其右下方的结点，一直走到底层，要求找出一条路径，使路径上的数字的和最大。
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
#include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N=600,I=1e9; int w[N][N]; int dp[N][N]; int main() { int n; cin>>n; for(int i = 1; i <= n ; i ++) for(int j = 1; j <= i ; j ++) cin>>w[i][j]; for(int i = 1; i <= n ; i ++) for(int j = 0; j <= i+1; j ++);//因为有负数，所以应该将两边也设为-INF dp[i][j]=-I; //因为有负数,所以应该初始化成负无穷 //如果初始化成 0 的话 //比如 数据范围只有一个元素-3，那就会从边界外的0转移过来 dp[1][1]=w[1][1]; for(int i = 2 ; i <= n ; i ++ ) for(int j = 1; j <= i ; j ++ ) dp[i][j]=max(dp[i-1][j-1],dp[i-1][j])+w[i][j]; int ans=-I for(int i = 1; i <= n ; i ++) ans=max(ans,dp[n][i]); cout<<ans<<endl; return 0; }
摘花生
A想摘点花生送给她喜欢的B。
她来到一片有网格状道路的矩形花生地(如下图)，从西北角进去，东南角出来。
地里每个道路的交叉点上都有种着一株花生苗，上面有若干颗花生，经过一株花生苗就能摘走该它上面所有的花生。
A只能向东或向南走，不能向西或向北走。
问A最多能够摘到多少颗花生。
第一行是一个整数T，代表一共有多少组数据。
接下来是T组数据。
每组数据的第一行是两个整数，分别代表花生苗的行数R和列数 C。
每组数据的接下来R行数据，从北向南依次描述每行花生苗的情况。每行数据有C个整数，按从西向东的顺序描述了该行每株花生苗上的花生数目M。
#include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N=200; int w[N][N]; int dp[N][N]; //存储的从（1，1）到（i，j）的所有方案的获取花生数量的最大值 int main() { int t; cin>>t; while(t--) { int n,m; cin>>n>>m; for(int i = 1; i <= n ; i ++) for(int j = 1; j <= m ; j ++) cin>>w[i][j]; for(int i = 1; i <= n ; i ++ ) for(int j = 1; j <= m ; j ++ ) { dp[i][j]=max(dp[i-1][j],dp[i][j-1])+w[i][j]; //划分关键最后一步怎么走的 最大数目 = max右到终点花生最大数目 从(1,1)到最后一步从左往 + 从(1,1)到最后一步从上往下到终点花生最大数目 //从(1,1)到[i-1][j]获取花生最大数目+终点w[i][j]花生的数 //从(1,1)到[i][j-1]获取花生最大数目+终点w[i][j]花生的数量 } cout<<dp[n][m]<<endl; } return 0; }
最小路径和
给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
示例 1：
输入：grid = [[1,3,1],[1,5,1],[4,2,1]] 输出：7 解释：因为路径 1→3→1→1→1 的总和最小。
#include<bits/stdc++.h> using namespace std; const int N = 1e3+10; int a[N][N],dp[N][N]; int main() { int n,m; cin>>n>>m; memset(dp,0x3f,sizeof(dp)); for(int i = 0 ; i < n ; i++) for(int j = 0 ; j < m ; j ++) cin>>a[i][j]; dp[0][1]=0; for(int i = 1 ;i <= n ; i ++) for(int j = 1 ;j <= m ; j ++) dp[i][j]=min(dp[i-1][j],dp[i][j-1])+a[i-1][j-1]; cout<<dp[n][m]; return 0; }
不同路径模型
机器人之能向下移或向右移，它想从M*N的网格里的左上角走到右下角，那总共有多少条路径？
#include<bits/stdc++.h> using namespace std; const int N=50; long long dp[N][N]; int main() { int x,y; cin>>x>>y; dp[0][1]=1;//初始化成 1 为了使起点有意义 //dp[1][1]=dp[0][1]+dp[1][0]=1+0=1; for(int i = 1 ; i <= x ; i ++) { for ( int j = 1 ; j <= y ; j ++) { dp[i][j]=dp[i-1][j]+dp[i][j-1]; dp[1][1]=dp[0][1]+dp[1][0]; //按照这个公式推肯定不行， //因为 f 的初始数值都是 0，再怎么推也都是 0， //先从起点下手，我们要让f(1,1)能根据上面得到的式子推出答案是 1（即起点到起点需要1步） //这样才能有得到意义的结果。 //所以我们需要 将 dp [1][0]或者 dp[0][1] 初始化成 1 即可 } } cout<<dp[x][y]; return 0; }
不同路径（有障碍）
机器人之能向下移或向右移，它想从M*N的网格里的左上角走到右下角，其中在坐标（a,b）位置有障碍物，要不碰障碍的前提下，他总共有多少条路径可以走？
#include<bits/stdc++.h> using namespace std; const int N=50; long long dp[N][N]; int main() { int x,y,a,b; cin>>x>>y>>a>>b; dp[0][1]=1; for(int i = 1; i <= x ; i ++) { for ( int j = 1 ; j <= y ; j ++) { if(i==a&&j==b)continue; //如果遇到障碍物，不进入递推，直接跳过进行下一个 //保持dp[a][b]初始状态就好 dp[i][j]=dp[i-1][j]+dp[i][j-1]; } } cout<<dp[x][y]; return 0; }
过河卒 (综合应用)
棋盘上 A点有一个过河卒，需要走到目标 B 点。卒行走的规则：可以向下、或者向右。同时在棋盘上 C 点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河卒”。
棋盘用坐标表示，A 点 (0,0)、B 点 (n,m)，同样马的位置坐标是需要给出的。
现在要求你计算出卒从 A 点能够到达 B 点的路径的条数，假设马的位置是固定不动的，并不是卒走一步马走一步。
1.初始化
dp[1][2]=1 //dp[2][2]=dp[1][2]+dp[2][1];
如果不初始话的话，按照这个公式推肯定不行，因为 dp 的初始数值都是 0，
再怎么推也都是 0，
我们要让dp [2] [2]=dp[1] [2]+dp[2] [1]
能根据上面得到的式子推出答案是 1，这样才能有有意义的结果。
我们只需要让 dp[1] [2]=1 或者 dp[2] [1]=1 即可。
注意这里的因为前面将所有坐标都 +2
所以（2，2） 是起点 dp【2】【2】=1 可以理解为只有一种方法到起点
#include<bits/stdc++.h> using namespace std; const int N=50; int pos[8][2]={2,1,2,-1,-2,1,-2,-1,1,2,-1,2,1,-2,-1,-2}; long long dp[N][N]; bool book[N][N]; int main() { int a,b,c,d; cin>>a>>b>>c>>d; a+=2,b+=2,c+=2,d+=2;//整体都 +2 防止数组越界（） book[c][d]=1;//先标记好马的位置 for(int i = 0 ; i < 8 ; i ++) { int x=c+pos[i][0],y=d+pos[i][1]; book[x][y]=1;//将马控制点都标记置好 } dp[1][2]=1;//初始化，为了使dp有意义 //dp[2][2]=dp[1][2]+dp[2][1]; for(int i = 2 ; i <= a ; i ++) { for ( int j = 2 ; j <= b ; j ++) { if(book[i][j])continue; //如果踩到标记点，不进入递推，直接跳过进行下一个 dp[i][j]=dp[i-1][j]+dp[i][j-1]; } } cout<<dp[a][b]; return 0; }
最长上升子序列模型
给定一个长度为 N 的数列，求数值严格单调递增的子序列的长度最长是多少。
7 3 1 2 1 8 5 6 • 1 • 2
4 • 1
题解部分：
dp [i]表示从第一个数字开始算，以a[i]结尾的最大的上升序列的个数。
若 a[j] 下一个数大于它的数是 a[i]
则 dp[i] 最长的上升子序列的长度 应该是 以a[j] 结尾的最长上升子序列的长度+1 即 dp[j]+1
要取此序列中最长的上升子序列
应该再把 每一个 dp[i] 取 max
const int N =1010; int a[N]; int dp[N];//dp[i]表示从第一个数字开始算，以a[i]结尾的最大的上升序列的个数。 int main() { int n; cin>>n; for(int i = 1 ; i <=n ; i ++ ) cin>>a[i]; int ans=0; for( int i = 1 ; i <= n ; i ++) { dp[i]=1; // 设的dp[i]至少为1，找不到前面数字小于自己的时候就为1 for(int j = 1 ; j <= i; j ++)//寻找 i 之前的上升子序列 if(a[j]<a[i])//必须保证上一个数小于a[i],才能是 上升子序列 { dp[i]=max(dp[i],dp[j]+1); //取出dp[j+1]的最大值 //因为以 a[i] 结尾的最长上升子序列 不是i 越大 子序列就越长 } ans=max(ans,dp[i]); } cout<<ans; return 0;
木棍加工
一堆木头棍子共有n根，每根棍子的长度和宽度都是已知的。棍子可以被一台机器一个接一个地加工。机器处理一根棍子之前需要准备时间。准备时间是这样定义的：
第一根棍子的准备时间为1分钟；
如果刚处理完长度为L，宽度为W的棍子，那么如果下一个棍子长度为Li，宽度为Wi，并且满足L>＝Li，W>＝Wi，这个棍子就不需要准备时间，否则需要1分钟的准备时间；
计算处理完n根棍子所需要的最短准备时间。比如，你有5根棍子，长度和宽度分别为(4, 9)，(5, 2)，(2, 1)，(3, 5)，(1, 4)，最短准备时间为2（按(4, 9)、(3, 5)、(1, 4)、(5, 2)、(2, 1)的次序进行加工）。
贪心+DP
1.先基于贪心的思想 ，按左端点升序排列，虽然升序排列，但不会影响大小关系。
然后看右端点，右端点所有上升子序列就是可以不用准备时间的，最小的准备时间就是右端点最小的降序序列个数
2.然后又有一个定理：下降子序列的个数等于最长上升子序列的长度，所以就可以直接转化成求最大上升子序列问题了。
#include<bits/stdc++.h> using namespace std; int ans; const int N=1e4; struct stu{ int x,y; }a[N]; int dp[N]; bool cmp(stu a,stu b) { if(a.x!=b.x) return a.x<b.x; return a.y<b.y; } int main(){ int n; cin>>n; //贪心处理 for(int i = 0 ; i < n ; i ++) cin>>a[i].x>>a[i].y; sort(a,a+n,cmp); //最长上升子序列问题 for(int i = 0; i < n ; i ++) { dp[i]=1; for(int j = 0 ; j < i ; j ++) if(a[j].x<a[i].x&&a[j].y>a[i].y)//对所有不大于下一点的 dp[i]=max(dp[i],dp[j]+1); ans=max(ans,dp[i]); } cout<<ans; }
导弹拦截
某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。
输入导弹依次飞来的高度（雷达给出的高度数据是≤50000 \le 50000≤50000的正整数），
1.计算这套系统最多能拦截多少导弹，
2.如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。
389 207 155 300 299 170 158 65
6 2
题解部分：
第一问：
每一发炮弹都不能高于前一发的高度，决定着一个系统 要想拦截最多的导弹，导弹的高度一应该是不上升的
所以第一问就转化成了 求解 最长不上升子序列的问题。
第二问：
一旦有上升的导弹，就需要新加一个系统来拦截，所以只需要最长上升子序列的个数就行了
#include<bits/stdc++.h> using namespace std; int t = 1,ans; const int N = 1e7+10; int dp[N],a[N],ans2; int main() { int x; while(cin>>a[t])t++; for(int i = 1 ; i < t ; i ++) { dp[i]=1; for(int j = 1 ; j < i ; j ++) { if(a[i]<=a[j]) dp[i]=max(dp[i],dp[j]+1); } ans=max(ans,dp[i]); } for(int i = 1 ; i < t ; i ++) { dp[i]=1; for(int j = 1 ; j < i ; j ++) { if(a[i]>a[j]) dp[i]=max(dp[i],dp[j]+1); } ans2=max(ans2,dp[i]); } cout<<ans<<"\n"<<ans2; return 0; }
完结散花
ok以上就是对 动态规划之线性DP 的全部讲解啦，很感谢你能看到这儿。如果有遗漏、错误或者有更加通俗易懂的讲解,欢迎小伙伴私信我，我后期再补充完善。
