基礎DP（三）——最長公共子序列LCS

定義

  子序列：在一個給定的序列中删去若幹個元素後得到的序列。

  子序列和子串是不同的概念，差別在于子串的元素在原序列中必須是連續的，但子序列不必，其元素在原序列在必須是按順序的但不一定連續。

  最長公共子序列： 給定兩個序列X和Y，當另一序列Z既是X的子序列，又是Y的子序列時，稱Z時序列X和Y的公共子序列。最長公共子序列就是長度最長的公共子序列。

DP算法

  定義狀态

dp[i][j]

表示X(i-1)和Y(i-1)的最長公共子序列。

  狀态轉移方程：

d p [ i ] [ j ] = { d p [ i − 1 ] j − 1 ] + 1 m a x ( d p [ i ] [ j − 1 ] , d p [ i − 1 ] [ j ] ) dp[i][j]=\left\{ \begin{aligned} &dp[i-1]j-1] + 1 \\ &max(dp[i][j-1], dp[i-1][j]) \end{aligned} \right. dp[i][j]={​dp[i−1]j−1]+1max(dp[i][j−1],dp[i−1][j])​

  (寫markdown的公式可折騰死我了T_T）

例題展示

  HDU 1159 Common Subsequence

  題解： 沒有題解，結合上述狀态轉移方程和代碼。

一般算法

#include<iostream>
#include<algorithm>
#include<string>
using namespace std;

int dp[1005][1005];
string s1,s2;
int LCS(){
    for (int i = 0; i < 1005; i++)
        for (int j = 0; j < 1005; j++)
            dp[i][j] = 0;
    for (int i = 1; i <= s1.length(); i++)
        for (int j = 1; j <= s2.length(); j++)
            if(s1[i-1] == s2[j-1])
                dp[i][j] = dp[i - 1][j - 1] + 1;
            else
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
    return dp[s1.length()][s2.length()];
}

int main(){
    while(cin >> s1 >> s2)
        cout << LCS() << endl;
    return 0;
}
           

滾動數組

#include<iostream>
#include<algorithm>
#include<string>
using namespace std;

int dp[1005];
int pre[1005];
string s1, s2;
int main(){
    while(cin >> s1 >> s2){
        for (int i = 0; i < 1005; i++)
            dp[i] = pre[i] = 0;
        for (int i = 1; i <= s1.length(); i++){
            for (int j = 1; j <= s2.length(); j++){
                if(s2[j-1] == s1[i-1])
                    dp[j] = pre[j - 1] + 1;
                else
                    dp[j] = max(dp[j - 1], pre[j]);
                pre[j - 1] = dp[j - 1];
            }
            pre[s2.length()] = dp[s2.length()];
        }    
        printf("%d\n", dp[s2.length()]);
    }
    return 0;
}