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

【題目敘述】https://zerojudge.tw/ShowProblem?problemid=c001
【解題想法】DP, 最長共同子序列 (Longest Common Subsequence, LCS)

  • 參考「Introduction to Algorithms」一書,有詳細的說明 (如下圖)。
  • 狀態轉移方程:程式碼第 18 行。

C++ 程式碼 (December 2019)

#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;
}

Python 程式碼 (August 2019)

while True:
    try:
        str1 = input()
        str2 = input()
        l1 = len(str1)
        l2 = len(str2)
        lst1 = [0] * (l1+1)
        lst2 = [0] * (l1+1)
        for i in range(l2):
            for j in range(l1):
                if str1[j] == str2[i]:
                    lst2[j+1] = lst1[j]+1
                else:
                    lst2[j+1] = max(lst2[j],  lst1[j+1])
            lst1 = lst2[:]
        print(lst2[-1])
    except:
        break
分享本文 Share with friends