NYOJ 36 &&HDU 1159 最長公共子序列(經典)

連結：​​click here​​

題意：tip：最長公共子序列也稱作最長公共子串(不要求連續)，英文縮寫為LCS（Longest Common Subsequence）。其定義是，一個序列 S ，如果分别是兩個或多個已知序列的子序列，且是所有符合此條件序列中最長的，則 S 稱為已知序列的最長公共子序列。

輸入

第一行給出一個整數N(0<N<100)表示待測資料組數

接下來每組資料兩行，分别為待測的兩組字元串。每個字元串長度不大于1000.

輸出

每組測試資料輸出一個整數，表示最長公共子序列長度。每組結果占一行。

樣例輸入

2
asdf
adfsd
123abc
abc123abc      

樣例輸出

3
6      

​

​

思路：引進一個二維數組dp[][]，用dp[i][j]記錄b[i]與d[j] 的LCS 的長度，b[i][j]記錄dp[i][j]是通過哪一個子問題的值求得的，我們是自底向上進行遞推計算，那麼在計算dp[i,j]之前，dp[i-1][j-1]，dp[i-1][j]與dp[i][j-1]均已計算出來。此時我們根據b[i] = d[j]還是b[i] !=d[j]，就可以計算出dp[i][j]。

代碼：

#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 1010;
int dp[maxn][maxn];
char b[maxn],d[maxn];
int main()
{
    int ncase;
    scanf("%d",&ncase);
    while(ncase--)
    {
        cin>>b>>d;
        int b1=strlen(b);
        int d1=strlen(d);
        for(int j=0; j<b1; j++)
            for(int k=0; k<d1; k++)
            {
                if(b[j]==d[k])
                    dp[j+1][k+1]=dp[j][k]+1;
                else
                    dp[j+1][k+1]=max(dp[j+1][k],dp[j][k+1]);
            }
        cout<<dp[b1][d1]<<endl;
    }
    return 0;
}