【範例】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 【題解】