dp最長公共子序列

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

首先，說明一下子序列的定義……

一個序列A=｛a1,a2,a3,...,an｝，從中删除任意若幹項，剩餘的序列叫A的一個子序列。

很明顯（并不明顯……），子序列……并不需要元素是連續的……（一開始的時候思維總是以為元素是連續的，好傻啊……）

然後是公共子序列……

如果C是A的子序列，也是B的子序列，那麼C是A和B的公共子序列……

公共子序列一般不止一個，最長的那個就是最長公共子序列，當然也可能不止一個……

煮個栗子……

A=｛1，3，6，9，5，4，8，7｝，B=｛1，6，3，4，5，7｝

｛1，4，7｝是A和B的公共子序列

｛1，3，4，7｝是A和B的最長公共子序列

好了，說明的部分就到這，接下來，進入解決問題的部分……

給出序列A=｛a1,a2,a3...an｝，B=｛b1,b2,b3...bn｝

我們用lcs[i][j]來表示A的前i項和B的前j項的最長公共子序列的長度

flag[i][j]表示這一點是由哪點繼承來的，然後，開始搜尋……

如果……

(1)A[i]==B[j]

那麼就代表lcs[i][j]的最後一項一定是A[i]，就是在lcs[i-1][j-1]接上A[i],也就是lcs[i][j]=lcs[i-1][j-1]+1，并記錄flag[i][j]

(2)A[i]!=B[j]

那麼lcs[i][j]=max(lcs[i-1][j-1],lcs[i][j-1])，因為既然接不上，那就繼承一個長一點的留着呗，不要忘記了flag[i][j]的數字是不同的親~

可能我說的比較簡略，上一張比較好了解的圖……

可能第一次看會很淩亂，仔細看吧親……

最後按flag打出來就好了~

最後上代碼

#include<stdio.h>
#include<string.h>
int lcs[1005][1005];
int flag[1005][1005];
char a[1005],b[1005];
void findlcs(char a[],char b[],int lena,int lenb){
    int i,j;
    for(i=1;i<=lena;i++)
        for(j=1;j<=lenb;j++){
            if(a[i-1]==b[j-1]){
                lcs[i][j]=lcs[i-1][j-1]+1;
                flag[i][j]=1;
            }
            else{
                if(lcs[i][j-1]>lcs[i-1][j]){
                    lcs[i][j]=lcs[i][j-1];
                    flag[i][j]=2;
                }
                else{
                    lcs[i][j]=lcs[i-1][j];
                    flag[i][j]=3;
                }
            }
        }
}
void printlcs(char a[],char b[],int lena,int lenb){
    int i=lena;
    int j=lenb;
    int len=0;
    int rec[1050];
    while(i>0&&j>0){
        if(flag[i][j]==1){
            rec[len++]=a[i-1];
            i--,j--;
        }
        else if(flag[i][j]==2) j--;
        else if(flag[i][j]==3) i--;
    }
    len--;
    while(len>=0){
        printf("%c",rec[len--]);
    }
    printf("\n");
}
int main(){
    while(~scanf("%s%s",a,b)){
        int lena=strlen(a);
        int lenb=strlen(b);
        findlcs(a,b,lena,lenb);
        printlcs(a,b,lena,lenb);
        memset(flag,0,sizeof(flag));
        memset(lcs,0,sizeof(lcs));
    }
    return 0;
}           

上兩個具體題目（題目出自buaacoding.cn）

Bamboo and the Ancient Spell

時間限制: 1000 ms 記憶體限制: 65536 kb

Problem description

The Hogwarts has set up a new course recently, giving you the ancient spells and requiring you to translate them into the modern ones. Every two ancient spells encode one modern spell.

Wizards and witches just point the ancient spells with the magic wands and speak loudly "THE LONGEST COMMON SUBSEQUENCE !", and they'll get the modern spell required：）

Ok, stop trying this muggles...Though we can't get the answers as quickly as they do, we can still decode them by coding ：）

So Bamboo will give you a lot of ancient spells( two in a group)，and hope you just return the LENGTH of the modern spell.

Attention please! The ancient spells may include strange characters '#' and '?'. They are too old to know their exact meanings, so we can just think that '#'s can not match any character while finding the answer, but '?' can match any character in the other ancient spell except '#'.

Input

The input file consists of several test cases.

Each test case includes 2 lines, one ancient spell per line.

The length of per ancient spell will less than 100 characters，and all characters are in upper case.

Output

For each case, output one line: the length of the modern spell.

sample input

ABCDE
ZBD
AC#EB
C#BFG
ACE#?
KIKI#A
???
?#?           

Sample output

2
2
1
2           

A TIP

emmmm, Can you guess what 'spell' means here? And what about the modern spells? Pay attention to what wizards and witches say when they use magic.

Another TIP

In case 2, '#' can not match any character, just like it doesn't exist, so the modern spell is "CB".

In case 3, '?' can match any character except '#', which means '?' can be seen as ‘A~Z' and '?' of course.

題目分析

這道題是最長公共子序列問題的一個簡單改編，本質上還是一個最長公共子序列問題，隻不過要在判斷字元相等時加一些條件。

用lcs[i][j]表示串a的前i個字元與串b的前j個字元的最長公共子序列長度

那麼，當a[i]與b[j]比對的時候

lcs[i][j]=lcs[i-1][j-1]+1

當a[i]與b[j]不比對的時候

lcs[i][j]=max{lcs[i-1][j-1],lcs[i][j-1]}

示例代碼

#include<stdio.h>
#include<string>
#include<iostream>
#include<cstring>
using namespace std;
int lcs[1005][1005];
char a[1005],b[1005];
int len_a,len_b;
void find_lcs(char a[],char b[],int len_a,int len_b)
{
    int i,j;
    for(i=1;i<=len_a;i++)
        for(j=1;j<=len_b;j++){
        if((a[i-1]!='#'&&b[j-1]!='#')&&(a[i-1]==b[j-1]||a[i-1]=='?'||b[j-1]=='?')){
            lcs[i][j]=lcs[i-1][j-1]+1;
        }
        else {
            if(lcs[i][j-1]>lcs[i-1][j]){
                lcs[i][j]=lcs[i][j-1];
            }
            else{
                lcs[i][j]=lcs[i-1][j];
            }
        }
    }
}
int main()
{
    while(scanf("%s %s",&a,&b)!=EOF)
    {
        len_a=strlen(a);
        len_b=strlen(b);
        memset(lcs,0,sizeof(lcs));
        find_lcs(a,b,len_a,len_b);
        printf("%d\n",lcs[len_a][len_b]);
    }
}