【筆記】DP:LCS 最長共同子序列

【範例】ZeroJudge c001: 10405 – Longest Common Subsequence題解

  • 讀入兩個字串 s1, s2。
  • dp[i][j]:s1 的前 i 個字元(s1[0] ~ s1[i-1]),與s2 的前 j 個字元(s2[0] ~ s2[j-1]),共同子序列的長度。
  • 【例】s1 = “abcdgh”,s2 = “aedfhr”,dp[4][3] = 2 ( “abcd” 與 “aed” 的共同子序列為 “ad” )
  • 更新 dp[i][j] 時,先比較 s1[i-1] 與 s2[j-1],
    • 如果兩個字元相同,則 dp[i][j] = dp[i-1][j-1] + 1;
    • 如果兩個字元不同,則 dp[i][j] = max(dp[i][j-1], dp[i-1][j]);
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

const int maxn=1005;
string s1, s2;
int dp[maxn][maxn];

int main() {
    int l1, l2;
    while (cin >> s1 >> s2) {
        l1 = (int)s1.length();
        l2 = (int)s2.length();
        memset(dp, 0, sizeof(dp));
        for (int i=1; i<=l1; i++) {
            for (int j=1; j<=l2; j++) {
                if (s1[i-1] == s2[j-1]) {
                    dp[i][j] = dp[i-1][j-1] + 1;
                } else {
                    dp[i][j] = max(dp[i][j-1], dp[i-1][j]);
                }
            }
        }
        cout << dp[l1][l2] << endl;
    }
    return 0;
}

【更多練習】HDU 1159 Common Subsequence 【題解

分享本文 Share with friends