dp总结

写这篇博文主要是为了归纳总结一下dp的有关问题（不定期更新，暑假应该会更的快一些）

会大概讲一下思路，不会事无巨细地讲

另一篇是平时做过的一些dp题，这篇博客里面提到的题都有题解放在那边：https://www.cnblogs.com/henry-1202/p/9211398.html 

这个玩意更新会有点慢，比较系统的学过一些dp的问题之后才会来写这个（可能要有人来催更才会写？）

一.最长上升子序列问题（LIS）

大概意思是给一个序列，按从左到右的顺序选出尽可能多的数，组成一个上升子序列（子序列：对于一个序列，在其中删除1个或多个数，其他数的顺序不变）

随便来个序列：1 8 7 4 8 9

它的最长上升子序列是1 4 8 9（当然也可以是1 7 8 9）

对于这个问题，有O(n²)做法和O(nlogn)做法，这里两个做法都会讲到

1.LIS的O(n²)做法

对于一个简单的LIS，你是怎么用肉眼判断的？一个一个往后找，然后数出最长的LIS，是不是？

n²做法就是用这种思路来做的，事实上这个做法就是一个优化后的暴力

设f[i]为以i为结尾的LIS的最大长度（也可以是起点），则有

f[i]=max(f[i],f[j]+1)(a[i]>a[j])

代码如下：

for(int i=1;i<=n;i++){
    f[i]=1;//这里不要忘记初始化，这是每个人都很容易忘记的地方
    for(int j=1;j<i;j++){
        if(a[i]>a[j])f[i]=max(f[i],f[j]+1);
    }
}

当然第二层循环也可以枚举j+1到n，都一样的，if里面的大于号改一下就好（这样的话就是f数组表示以a_i为起点的最长上升子序列的）

这五行代码是LIS的基本模型，基本所有LIS的题都是对这五行代码添添改改搞出来的，所以在学习下面的东西之前需要务必确保自己完全搞懂这五行代码了再继续看

确保自己搞懂了之后可以先做一下例题中的合唱队形还有导弹拦截的n²做法

2.LIS的O(nlogn)做法

 在学习LIS的nlogn做法之前，你需要两个前置姿势：知道什么是贪心，并且会打二分查找

想想LIS：在一个序列中选出尽可能多的数组成一个上升子序列。

让我们用用贪心的思想：

对于n²做法，我们是在求出以a_i为结尾（起点）的LIS，以不断更新f数组的值的方式来维护LIS，而在这个过程中，f数组的值一定是最优的，而对于LIS来说，最优意味着什么？

对于最优的LIS，它的最后一位一定是尽可能小的，因为这样在后面更新的过程中，你才有更大的可能性让这个LIS变得更长

LIS的nlogn做法就是根据这种思想来做的，然后通过二分查找来使效率降到nlogn

相应的，f数组的含义也需要改一下：f_i代表长度为i的LIS的最后一位数

在看代码之前请确保你理解了上面的贪心的思路

int m=1;//m是指LIS的长度，m=1是因为LIS的长度至少为1
memset(f,127,sizeof(f));//初始化，这里的127表示的是无穷大
f[1]=a[1];//初始化
for(int i=2;i<=n;i++){
    if(a[i]>f[m])f[++m]=a[i];//如果比当前的LIS的最后一位还大那这个LIS就可以变长了
    else {//通过二分查找来更新f数组
        int l=0,r=m;
        while(l<r){
            int mid=(l+r)>>1;
            if(a[i]>f[mid])r=mid;
            else l=mid+1;
        }
        f[l]=a[i];//不要忘记更新
    }
}

 想练一下LIS的nlogn做法的话就去试试洛谷的导弹拦截吧，可以去我的另一篇博客看题解qwq，链接在上面

 二,最长公共子序列（LCS）

公共子序列是指：一个同时是这两个序列的子序列的序列

有点绕口...反正就是那个意思

例如：

1 2 3 4 5

2 1 3 5 4

LCS的长度显然是3（1,3,4/2,3,4）

于是可以设f[i][j]表示第一个序列的前i位与第二个序列的前j位的LCS

答案就是f[len1][len2]

转移方程其实很好想的：

如果第一个序列的i位与第二个序列的j位相同，那么转移：f[i][j]=max(f[i-1][j],f[i][j-1])+1

如果不同那么考虑继承之前的最优答案：f[i][j]=max(f[i-1][j],f[i][j-1])

这里给例题中的 洛谷P1439[模板]最长公共子序列 的朴素LCS做法

#define ll int
#define N 1010
ll n,a[N],b[N],f[N][N];
int main(){
    scanf("%d",&n);
    for(ll i=1;i<=n;i++)scanf("%d",&a[i]);
    for(ll i=1;i<=n;i++)scanf("%d",&b[i]);
    for(ll i=1;i<=n;i++){
        for(ll j=1;j<=n;j++){
            if(a[i]==b[j])f[i][j]=max(f[i-1][j],f[i][j-1])+1;
            else f[i][j]=max(f[i-1][j],f[i][j-1]);
        }
    }
    printf("%d",f[n][n]);
    return 0;
}

然后这道题的100%做法是很妙的，有兴趣的话可以去做一下（上面的做法只能50分）

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有