文章原链接: 【笔记】线性DP - OIer:ccr39の博客 - 洛谷博客 (luogu.com.cn)
一、定义
线性$DP$,指利用线性结构对问题进行求解的一种常见的动态规划类型。
对于线性$DP$ ，一般没有固定的模板，需要根据题意与状态进行逐步求解。
线性动态规划的目标函数为特定变量的线性函数，约束是这些变量的线性不等式或等式，目的是求目标函数的最大值或最小值。
因此，除了少量问题（如：LIS、LCS、LCIS等）有固定的模板外，大部分都要根据实际问题来推导得出答案。
二、常见问题
对于线性$DP$一般有以下常见模板题型：
1、最长单调上升子序列（洛谷AT2827 LIS）
（1）题目
- 给定一个长为$n$ 的序列 $a_i$，求这个序列的单调上升子序列长度。
- $1 \le a_i \le n \le10^5$。
（2）做法
$solution~1:O(n^2)$
线性$DP$，根据我们之前介绍过得$DP$三连可以得到以下思路。
我是谁？（设计状态）
我们考虑使用$DP[i]$来表示第以i位结尾的最长的单调上升子序列长度。
即：我是第i位之前的最长单调上升子序列的长度。
我从何而来 (backward 型转移)
我将到何方 (forward 型转移)
对于本题来说，我们采用第一种转移方式，考虑我是如何求得。
我们可以发现，对于任何一个点$dp_i$来说，以它为结尾的最长单调上升子序列的长度就是在它之前的，元素值小于它的所有点的最大值+1。
即对于一个点$a_j(0\le j< i)$若$a_j<a_i$且在所有满足条件的j中,$dp_j$的值最大，那么，$dp_i=dp_j+1$。
把写出它的状态转移方程：
$dp_i=max(dp_j)+1(0\le j< i,a_j<a_i );dp_0=0$
这样，我们就能求出每个阶段下最长的单调上升序列，再存储其最大值即可。
时间复杂度$O(n^2)$
$code~1:$
#include<bits/stdc++.h>
#define re register
#define rint re int
const int MAXN=1e5+5;
int n,ans,a[MAXN],dp[MAXN];
signed main()
{
scanf("%d",&n);
for(rint i=1;i<=n;i++)
scanf("%d",&a[i]);
for(rint i=1;i<=n;i++)
{
for(rint j=1;j<i;j++)
if(a[j]<a[i])
dp[i]=max(dp[i],dp[j]);
ans=max(ans,++dp[i]);
}
printf("%d",ans);
return 0;
}
$solution~2:O(nlogn)$
利用二分的思想，去维护一个单调递增的序列。
对于每一次的元素的插入，都利用二分查找其位置。
时间复杂度$O(nlogn)$
$code$ $2:$
#include<bits/stdc++.h>
#define re register
#define rint re int
const int MAXN=1e5+5;
int n,a[MAXN],f[MAXN],p=1;
signed main()
{
scanf("%d",&n);
for(rint i=1;i<=n;i++)
scanf("%d",&a[i]);
f[p]=a[1];//把a[1]先放入数组中
for(rint i=2;i<=n;i++)
if(a[i]>f[p]) f[++p]=a[i];//如果a[i]>s[p]也就是比现有元素都大，就直接将其插入到数组最后
else f[lower_bound(f+1,f+p+1,a[i])-f]=a[i];//在f中查找正好大于或等于a[i]的位置，并将其替换。lower_bound查找大于等于，upper_bound查找大于，两者初始仅可以在单调递增的序列中查询。
printf("%d",p);
return 0;
}
$solution$ $3:$
树形数组，对$DP$的一种优化方式，时间复杂度$O(nlogn)$,但常数比第二种方法大。
（3）同类题型:P1020导弹拦截、P1091合唱队形。
2、最长公共子序列$LCS$(P1439)
（1）题目
- 给定两个长为$n$ 的序列$P_1$ 和 $P_2$ ，求它们的最长公共子序列。
- $1 \le n \le10^5$。
（2）做法
$solution1：O(n^2)$
线性$DP$，我们继续按照之前做题的思路，使用$DP$三连分析问题。
我是谁？（设计状态）
我们考虑使用$DP[i][j]$来表示$a_{1∼i},b_{1∼j}$的LCS长度。
即：我是第$a$的第i位之前,和b的第$j$位前，$a,b$的最长公共子序列。
我从何而来 (backward 型转移)
我将到何方 (forward 型转移)
这里我们依旧选择第二种转移方式解决此题。
我们来思考，当$a[i]=b[j]$时,那么就表示有新的公共元素，那么
$dp[i][j]=dp[i-1][j-1]+1$
如果没有新的公共元素，那么就要继承之前的值
$dp[i][j]=max(dp[i−1][j],dp[i][j−1])$
那么我们就可以写出来它的状态转移方程。
$code~1:$
#include<iostream>
using namespace std;
int dp[1001][1001],a[2001],b[2001],n,m;
int main()
{
cin>>n;
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
for(int i=1;i<=n;i++)scanf("%d",&b[i]);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(a[i]==b[j]) dp[i][j]=dp[i-1][j-1]+1;
else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
cout<<dp[n][n];
}
$solution~2:O(nlogn)$
将问题转化成$LIS$,将$a$序列映射进一个数组里，数组下标代表a序列的数，而数组的值表示其下标在$a$数组的位置。
即若 $a_1=3,a_2=2,a_3=1,a_4=4,a_5=5$
那么$map_1=3,map_2=2,map_3=1,map_4=4,map_5=5$
那么在根据$b$数组在$map$数组中的相对位置做$LIS$。
得到的就是他们的$LCS$。
换句话说，只要$b$中某个子序列在$a$中的相对位置单调递增，那么它就是$a$的子序列。
当$b_1=1,b_2=2,b_3=3,b_4=4,b_5=5$时
$b_1$的位置在$a$中排第3位，$b_2$的的位置在$a$中排第2位,$b_3$的位置在$a$中排第1位，$b_4$的位置在$a$中排第4位,$b_5$的位置在$a$中排第5位。
(也可以写成$map_{b_1}=3,map_{b_2}=2,map_{b_3}=1,map_{b_4}=4,map_{b_5}=5$)
在此之中，最长单调上升子序列为$1,4,5$,那么相对应的,$b$与$a$的$LCS$就是$b_3,b_4,b_5$。
时间复杂度$O(nlogn)$,但仅限于全排列数组。
$code~2:$
#include<bits/stdc++.h>
#define re register
#define rint re int
using namespace std;
const int MAXN=1e6+5;
int a,b[MAXN],Map[MAXN],dp[MAXN];
int main()
{
rint n,len=0;
scanf("%d",&n);
for(rint i=1;i<=n;i++)
scanf("%d",&a),Map[a]=i;
for(rint i=1;i<=n;i++)
scanf("%d",&b[i]),dp[i]=0x7fffffff;//因为要查找位置，所以dp要赋极大值
for(rint i=1;i<=n;i++)
if(Map[b[i]]>dp[len]) dp[++len]=Map[b[i]];//如果可以直接满足递增，则直接插入尾部
else
{
rint k=lower_bound(dp+1,dp+len+1,Map[b[i]])-dp;
dp[k]=Map[b[i]];//如果不行，则插入到第一个大于等于本身的地方
}
printf("%d",len);
return 0;
}
（3）同类题目：AT4527 LCS
3、最长公共子上升序列(CF10D LCIS)
（1）题目
- 给定两个长分别为$n、m$ 的序列$P_1$ 和 $P_2$ ，求它们的最长公共上升子序列。
- $1 \le n,m \le500$。
（2）做法
待补充（鸽了）
