動态規劃———最長公共子序列（LCS）

最長公共子序列;

言簡意赅就是在兩個序列a，b裡找同時是a,b兩個序列的子序列并且相同的長度最長的那個。

我們用一個二維的dp[i][j]去表示以a[i]結尾和以b[j]結尾的最長的公共子序列的長度。

這樣的話就可以很容易得到更新的dp[i][j]的方程。

我們來了解這個方程為什麼是這個樣子的，

dp[i][j]表示的是以a[i]結尾的子序列和以b[j]結尾的子序列的最長長度。

那麼，我們來想一下dp[i][j]是從那些地方更新過來的。

一個二維數組要更新而且還是和他的前一個狀态有關系則肯定隻有三個地方更新得到dp[i-1][j-1],dp[i][j-1],dp[i-1][j]三個方向更新過來。

那三個狀态分别表示什麼呢？

dp[i-1][j-1]: 以a[i-1]結尾的子序列與b[j-1]結尾的子序列的最長公共子序列。

dp[i][j-1]: 以a[i]結尾的子序列與b[j-1]結尾的子序列的最長公共子序列。

dp[i-1][j]: 以a[i-1]結尾的子序列與b[j]結尾的子序列的最長公共子序列。

是以：

如果目前比較的兩個元素是一樣的則：目前的長度可以在不包含這兩個元素的最長公共子序列的基礎上長度+1。

但是如果目前比較元素不一樣，則為了是的現在的長度任是最長的就要去繼承之前的兩個比較長的那一種情況。

模闆題目 HDU-1159

ac code:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <algorithm>
using namespace std;
const int maxn = 1e4+10;
int dp[maxn][maxn];
int main()
{
    string a,b;
    while(cin>>a>>b){
        dp[0][0]=0;
        int alen = a.size();
        int blen = b.size();
        for(int i=0;i<alen;i++){
            for(int j=0;j<blen;j++){
                if(a[i]==b[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]);
                }
            }
        }
        cout<<dp[alen][blen]<<endl;
    }

}

           

列印出來最長的序列是什麼 POJ - 2250

我們可以在确定最長長度之後往回退就好了 在相等的地方記錄一下。

ac code:

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
using namespace std;
const int maxn =110;
int dp[maxn][maxn];
char a[maxn][40];
char b[maxn][40];
string ans[maxn];
int main()
{
    char s[maxn];
    while(~scanf("%s",s)){
        memset(dp,0,sizeof(dp));
        dp[0][0]=0;
        int cnt_a=0,cnt_b=0,cnt=0;
        strcpy(a[cnt_a++],s);
        while(1){
            scanf("%s",s);
            if(strcmp(s,"#")==0)break;
            strcpy(a[cnt_a++],s);
        }
        while(1){
            scanf("%s",s);
            if(strcmp(s,"#")==0)break;
            strcpy(b[cnt_b++],s);
        }
        for(int i=0;i<cnt_a;i++){
            for(int j=0;j<cnt_b;j++){
                if(strcmp(a[i],b[j])==0){
                    dp[i+1][j+1]=dp[i][j]+1;
                }
                else{
                    dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j]);
                }
            }
        }
        // cout<<dp[cnt_a][cnt_b]<<endl;
        // for(int i=0;i<cnt_a;i++){
        //     cout<<a[i]<<endl;
        // }
        // for(int i=0;i<cnt_b;i++){
        //     cout<<b[i]<<endl;
        // }
        int i=cnt_a,j=cnt_b;
        while(dp[i][j]){
            if(strcmp(a[i-1],b[j-1])==0){
                ans[cnt++]=a[i-1];
                i--;j--;
            }
            else if(dp[i][j-1]>dp[i-1][j]){
                j--;
            }
            else{
                i--;
            }
        }
        for(int i=cnt-1;i>=0;i--){
            if(i==0)cout<<ans[i]<<endl;
            else cout<<ans[i]<<" ";
        }
    }


    return 0;
}

           

HDU - 1503

**題意:**給你兩個字元串你要找到最短的包含這兩個字元串，并且字元順序不變。

思路：這就是最長公共子序列的變形，你想一下，要使的求的的字元串最短當然要最長公共子序列因為他們一個頂兩啊，

ac code:

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstring>
using namespace std;
const int maxn =110;
int dp[maxn][maxn];
int main()
{
    string a,b,ans;
    while(cin>>a>>b){
        int alen = a.size();
        int blen = b.size();
        ans="";
        dp[0][0]=0;
        for(int i=0;i<alen;i++){
            for(int j=0;j<blen;j++){
                if(a[i]==b[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]);
            }
        }
        int i=alen,j=blen;
        while(dp[i][j]){
            if(a[i-1]==b[j-1]){
                ans+=a[i-1];
                i--,j--;
            }
            else if(dp[i][j-1]>dp[i-1][j]){
                ans+=b[j-1];
                j--;
            }
            else {
                ans+=a[i-1];
                i--;
            }
        }
        while(i!=0){
            ans+=a[i-1];
            i--;
        }
        while(j!=0){
            ans+=b[j-1];
            j--;
        }
        for(int i=ans.size()-1;i>=0;i--)
        cout<<ans[i];
        cout<<endl;
    }
    return 0;
}

           

如有錯誤，望評論或私信指正，感激不盡。