【題目敘述】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