文章原链接: 【笔记】线性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$三连可以得到以下思路。

  1. 我是谁?(设计状态)

    我们考虑使用$DP[i]$来表示第以i位结尾的最长的单调上升子序列长度。

    即:我是第i位之前的最长单调上升子序列的长度。

  2. 我从何而来 (backward 型转移)

  3. 我将到何方 (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)$,但常数比第二种方法大。

详解可见此。(@星爵$dalao$)

(3)同类题型:P1020导弹拦截P1091合唱队形


2、最长公共子序列$LCS$(P1439)

(1)题目

  • 给定两个长为$n$ 的序列$P_1$ 和 $P_2$ ,求它们的最长公共子序列。
  • $1 \le n \le10^5$。

(2)做法

$solution1:O(n^2)$

线性$DP$,我们继续按照之前做题的思路,使用$DP$三连分析问题。

  1. 我是谁?(设计状态)

    我们考虑使用$DP[i][j]$来表示$a_{1∼i},b_{1∼j}$的LCS长度。

    即:我是第$a$的第i位之前,和b的第$j$位前,$a,b$的最长公共子序列。

  2. 我从何而来 (backward 型转移)

  3. 我将到何方 (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)做法

待补充(鸽了)


I am ordinary yet unique.