【笔记】线性DP

· · 个人记录

一、定义

线性DP,指利用线性结构对问题进行求解的一种常见的动态规划类型。

对于线性DP​ ，一般没有固定的模板，需要根据题意与状态进行逐步求解。

二、常见问题

对于线性DP​​一般有以下常见模板题型：

1、最长单调上升子序列（洛谷AT2827 LIS）

（1）题目

（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）题目

（2）做法

solution~1：~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]=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​时

(也可以写成$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）题目

（2）做法

待补充（鸽了）