alan23273850 的刷題筆記
d674: 10192 - Vacation
出處：https://zerojudge.tw/ShowProblem?problemid=d674
提交：https://zerojudge.tw/Submissions?problemid=d674&account=allllllan123456
問題：給定兩個長度分別介於 $[1,100]$ 而且僅由大小寫英文字母、數字、空白字元 (共 63 種字元) 組成的字串，請求出它們的最長共同子序列長度？
解法：就很經典可以用 DP 解決的老問題，top down recursion 寫起來很簡潔，另外因為有多次輸入所以每次的 dp 陣列都要記得初始化，然後讀取方式也要因應空白字元的出現而改用 getline。
1#include <bits/stdc++.h>
2using namespace std;
3
4int dp[100][100];
5string str1, str2;
6
7int lcs(int x, int y) {
8 if (x<0 || y<0) return 0;
9 if (dp[x][y] >= 0) return dp[x][y];
10 if (str1[x] == str2[y]) return dp[x][y] = lcs(x-1, y-1) + 1;
11 return dp[x][y] = max(lcs(x-1, y), lcs(x, y-1));
12}
13
14int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); // IO 優化
15 int T = 0;
16 while (getline(cin, str1) && str1!="#") {
17 getline(cin, str2); memset(dp, -1, sizeof dp);
18 cout << "Case #" << ++T << ": you can visit at most " << lcs(str1.length()-1, str2.length()-1) << " cities.\n";
19 }
20 return 0;
21}