前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >线性DP总结(LIS,LCS,LCIS,最长子段和)

线性DP总结(LIS,LCS,LCIS,最长子段和)

作者头像
ShenduCC
发布2018-04-26 11:14:08
1.6K0
发布2018-04-26 11:14:08
举报
文章被收录于专栏:算法修养

做了一段时间的线性dp的题目是时候做一个总结 线性动态规划无非就是在一个数组上搞嘛, 首先看一个最简单的问题: 一,最长字段和 下面为状态转移方程

代码语言:javascript
复制
       for(int i=2;i<=n;i++)
        {
              if(dp[i-1]>=0)
                  dp[i]=dp[i-1]+a[i];
              else
                  dp[i]=a[i];
        }

例题 裸的最长字段和 可以用滚动数组,下面是用滚动数组写的

代码语言:javascript
复制
#include <iostream>
#include <algorithm>
#include <string.h>
#include <math.h>
#include <stdlib.h>

using namespace std;
int n;
int a;
int sum;
int _begin;
int _end;

int main()
{
    int t;
    scanf("%d",&t);
    int k=0;
    while(t--)
    {
        int max;
        int x=1;
        scanf("%d%d",&n,&a);
        sum=a;
        max=a;
        _begin=_end=1;
        for(int i=2;i<=n;i++)
        {
            scanf("%d",&a);
            if(sum>=0)
            {
                sum+=a;
            }
            else
            {
                sum=a;
                x=i;
            }
            if(max<sum)
            {
                max=sum;
                _begin=x;
                _end=i;
            }

        }
          cout<<"Case "<<++k<<":"<<endl<<max<<" "<<_begin<<" "<<_end<<endl; 
        if(t)
            cout<<endl;


    }
    return 0;
}

升级一下,二维的呢?也就是求最大子矩阵和 状态转移方程,其实就是将一维转换成二维的,如何转换呢?操作就是将第一行每个数加上第二行对应的每个数,变成一维的进行dp,再加上第三行对应的每个数,进行DP。起点行分别枚举从1到n。

代码语言:javascript
复制
     for(int i=1;i<=n;i++)
       {
           memset(b,0,sizeof(b));
           memset(dp,0,sizeof(dp));
           for(int k=i;k<=n;k++)
           {
               for(int j=1;j<=n;j++)
               {
                   b[j]+=a[k][j];
                   if(dp[j-1]>=0)
                       dp[j]=dp[j-1]+b[j];
                   else
                       dp[j]=b[j];
                   if(sum<dp[j])
                       sum=dp[j];
               }
           }

       }

例题

代码语言:javascript
复制
#include <iostream>
#include <math.h>
#include <string.h>
#include <algorithm>
#include <stdlib.h>

using namespace std;
int a[105][105];
int n;
int dp[105];
int b[105];
int sum;
int main()
{
   while(scanf("%d",&n)!=EOF)
   {
       sum=0;
       for(int i=1;i<=n;i++)
       {
           for(int j=1;j<=n;j++)
           {
               scanf("%d",&a[i][j]);
           }
       }
       for(int i=1;i<=n;i++)
       {
           memset(b,0,sizeof(b));
           memset(dp,0,sizeof(dp));
           for(int k=i;k<=n;k++)
           {
               for(int j=1;j<=n;j++)
               {
                   b[j]+=a[k][j];
                   if(dp[j-1]>=0)
                       dp[j]=dp[j-1]+b[j];
                   else
                       dp[j]=b[j];
                   if(sum<dp[j])
                       sum=dp[j];
               }
           }

       }
       printf("%d\n",sum);

   }
    return 0;
}

接下来就是LIS问题,LIS就是最长下降子序列或者是最长上升子序列。有O(n^2)效率的算法,也有O(nlogn)效率的算法。 先说O(n^2)效率的算法。很简单,DP[j] = MAX(DP[i]) + 1 满足条件a[j] > a[i] 转态转移方程

代码语言:javascript
复制
     for(int i=2;i<=n+1;i++)
        {
            int num=0;
            for(int j=i-1;j>=1;j--)
            {
                if(a[i]>a[j])
                    num=max(num,dp[j]);
            }
            dp[i]=num+1;
        }

O(nlogn)效率的算法,参考这篇博文 博文 其实过程很简单,以最长上升子序列为例。dp数组的最终长度就是最长上升子序列,遍历a数组,a[i]如果比dp数组最后一个元素大,即a[i]>dp[len]则直接加入dp数组里。否则就要二分查找到第一个小于a[i]的dp[j],然后将dp[j]换成a[i],最终的dp数组的长度就是答案。 例题

代码语言:javascript
复制
#include <iostream>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <stdlib.h>

using namespace std;
#define MAX 40000
int a[MAX+5];
int dp[MAX+5];
int n;
int search(int num,int l,int r)
{
    int mid;
    while(l<=r)
    {
        mid=(l+r)/2;
        if(num>=dp[mid])
            l=mid+1;
        else
            r=mid-1;
    }
    return l;
}
int main()
{
    int cas=0;
    int x,y;
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);

        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);

        }
        memset(dp,0,sizeof(dp));
        dp[1]=a[1];
        int len=1;
        for(int i=2;i<=n;i++)
        {
            if(a[i]>=dp[len])
                dp[++len]=a[i];
            else
            {
                int pos=search(a[i],1,len);
                dp[pos]=a[i];
            }
        }
        printf("%d\n",len);
    }
    return 0;
}

还有一个比较相似的求最长连续上升子序列或最长连续下降子序列。求解这个就不用DP了,应该用线段树。

接下来就是LCS,最长公共子序列问题,这个也有O(n^2)的效率和O(nlogn)的效率 O(n^2)效率的看代码

代码语言:javascript
复制
      for(int i=0;i<len1;i++)
        {
            for(int j=0;j<len2;j++)
            {
                if(s1[i]==s2[j])
                    dp[i+1][j+1]=dp[i][j]+1;
                else
                    dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j]);

            }
        }

O(nlogn)效率是把LCS转化成LIS问题 a[] = {a, b, c,} b[] = {a,b,c,b,a,d},那么a中的a,b,c在b中出现的位置分别就是{0,4},{1,3},{2}分别按降序排列后代入a序列就是{4,0,2,3,1},

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2016-01-23 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档