幾種線性DP（最長上升子序列，最長公共子序列等）

1.最長上升子序列

//最長上升子序列，O(n^2)算法
for(int i=1;i<=n;i++)
{
    scanf("%d",&a[i]);
    dp[i]=1;
}
int ans=0;
for(int i=1;i<=n;i++)
{
    for(int j=1;j<i;j++)
    {
        if(a[i]>a[j])   //嚴格
            dp[i]=max(dp[i],dp[j]+1);
        /*
        if(a[i]>=a[j])   //非嚴格
            dp[i]=max(dp[i],dp[j]+1);
        */
    }
    ans=max(dp[i],ans);
}

//最長上升子序列，O(nlogn)算法
for(int i=1;i<=n;i++)
    scanf("%d",&a[i]);
dp[1]=a[1];    //dp[i]=代表長度為i的串結尾數字最小的數是x
int len=1;
for(int i=2;i<=n;i++)
{
    if(a[i]>dp[len])  //嚴格
        dp[++len]=a[i];
    else
    {
        int pos=upper_bound(dp+1,dp+1+len,a[i])-dp; //找到>a[i]的第一個元素，并用a[i]替換,每次通過替換前面大的數值來得到更優的結果
        dp[pos]=a[i];
    }
    /*
    if(a[i]>=dp[len])  //非嚴格
        dp[++len]=a[i];
    else
    {
        int pos=lower_bound(dp+1,dp+1+len,a[i])-dp; //找到>=a[i]的第一個元素，并用a[i]替換,每次通過替換前面大的數值來得到更優的結果
        dp[pos]=a[i];
    }
    */
}
           

2.最長公共子序列

//最長公共子序列
scanf(" %s %s",a+1,b+1));
int x=strlen(a+1);
int y=strlen(b+1);
//cout<<"x="<<x<<"y="<<y<<endl;
dp[0][1]=0;    //dp[i][j]代表a長度為i，b長度為j的最長公共子序列
dp[1][0]=0;
dp[0][0]=0;
for(int i=1;i<=x;i++)
{
    for(int j=1;j<=y;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]);
    }
}
           

3.最長公共上升子序列

//最長公共上升子序列

//二維數組存
scanf("%d",&n);
for(int i=1;i<=n;i++)
    scanf("%d",&a[i]);
scanf("%d",&m);
for(int i=1;i<=m;i++)
    scanf("%d",&b[i]);
dp[0][0]=0;
dp[0][1]=0;
dp[1][0]=0;
int ans=0;
for(int i=1;i<=n;i++)
{
    int MAX=0;    //更新當a[i]==b[j]時能得到的最長的公共上升子序列
    for(int j=1;j<=m;j++)
    {
        if(a[i]!=b[j])
        {
            dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
            if(a[i]>a[j])          //目前a[i]比b[j]大的，那麼找到相等的b[j]的時候一定也比目前b[j]大
                MAX=max(MAX,dp[i-1][j]);
        }
        else
            dp[i][j]=MAX+1;
        ans=max(ans,dp[i][j]);
    }
}

//一維數組存，類似01背包滾動,可以優化空間
scanf("%d",&n);
for(int i=1;i<=n;i++)
    scanf("%d",&a[i]);
scanf("%d",&m);
for(int i=1;i<=m;i++)
    scanf("%d",&b[i]);
memset(dp,0,sizeof(dp));
int ans=0;
for(int i=1;i<=n;i++)
{
    int MAX=0;
    for(int j=1;j<=m;j++)
    {
        if(a[i]>b[j])
            MAX=max(MAX,dp[j]);
        if(a[i]==b[j])
            dp[j]=MAX+1;
        ans=max(ans,dp[j]);
    }
}
           

最長公共上升子序列推薦一篇部落格： 連結傳送門