alan23273850 的刷題筆記
d231: 97北縣賽-2-基因序列密碼問題
出處：https://zerojudge.tw/ShowProblem?problemid=d231
提交：https://zerojudge.tw/Submissions?problemid=d231&account=allllllan123456
問題：給定兩個長度分別介於 $[1,50]$ 而且僅由 A、C、G、T 四個英文字母組成的字串，請求出它們的最長共同子序列？
解法：就很經典可以用 DP 解決的老問題，而且因為這題要把子序列印出來但 size 又不大，我就嘗試著把函式回傳值直接改成當下的最長子序列，寫起來也蠻簡潔漂亮，一般教科書不會這樣教的。
1#include <bits/stdc++.h>
2using namespace std;
3
4string str1, str2, dp[50][50];
5
6string lcs(int x, int y) {
7 if (dp[x][y].length()) return dp[x][y];
8 if (!x && !y) return (str1[x]==str2[y]) ? string{str1[x]} : "";
9 if (!x) {
10 if (str1[x] == str2[y]) return dp[x][y] = str1[x];
11 return dp[x][y] = lcs(x, y-1);
12 }
13 if (!y) {
14 if (str1[x] == str2[y]) return dp[x][y] = str1[x];
15 return dp[x][y] = lcs(x-1, y);
16 }
17 if (str1[x] == str2[y]) return dp[x][y] = lcs(x-1, y-1) + str1[x];
18 string a = lcs(x-1, y), b = lcs(x, y-1);
19 return dp[x][y] = (a.length() > b.length()) ? a : b;
20}
21
22int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); // IO 優化
23 cin >> str1 >> str2;
24 string ans = lcs(str1.length()-1, str2.length()-1);
25 cout << (ans.length() ? ans : "E") << '\n';
26 return 0;
27}