基础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;
}