alan23273850 的刷題筆記
c001: 10405 - Longest Common Subsequence
出處：https://zerojudge.tw/ShowProblem?problemid=c001
提交：https://zerojudge.tw/Submissions?problemid=c001&account=allllllan123456
問題：給定兩個長度分別介於 $[1,1000]$ 的字串，請求出它們的最長共同子序列長度。
解法：就很經典可以用 DP 解決的老問題，不知道為什麼這題用 top down 方式跑起來的記憶體用量看起來遠大於 bottom up 方式，可能是因為 recursion overhead？於是這題我採用經典的 bottom up 填表作法，而且一個 row 一個 row 按照順序填寫的話還可以壓在總共兩個 row 裡面完成，是很有名的作法。
1#include <bits/stdc++.h>
2using namespace std;
3
4int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); // IO 優化
5 string str1, str2; short lcs[2][1000];
6 while (cin >> str1 >> str2) {
7 lcs[0][0] = str1[0] == str2[0];
8 for (int j=1; j<str2.length(); j++) lcs[0][j] = max(lcs[0][j-1], short{str1[0]==str2[j]});
9 for (int i=1; i<str1.length(); i++) { bool r = i & 1;
10 lcs[r][0] = max(lcs[r^1][0], short{str1[i]==str2[0]});
11 for (int j=1; j<str2.length(); j++)
12 lcs[r][j] = str1[i]==str2[j] ? lcs[r^1][j-1] + 1 : max(lcs[r^1][j], lcs[r][j-1]);
13 }
14 cout << lcs[(str1.length()-1)&1][str2.length()-1] << '\n';
15 }
16 return 0;
17}