題意#
給定兩個由整數組成的陣列。你的任務是找出這兩個陣列的「最長共同子序列」（Longest Common Subsequence，簡稱 LCS）。
要注意的是，子序列跟子字串/子陣列不同，子序列「不需要連續」，只要裡面的元素在原本陣列中的相對順序保持一致即可。
題目不僅要求你輸出這個最長共同子序列的長度，還要把這個子序列實際的內容也找出來並印出。
思路#
這題在經典的 LCS 基礎之上，多了一個「回溯（Backtracking）」找出實際序列的要求。
首先是求長度的部分：我們可以定義一個二維陣列 v（通常習慣叫 dp），其中 v[i][j] 代表「第一個陣列前 i 個元素」和「第二個陣列前 j 個元素」的最長共同子序列長度。
- 當兩個當前元素相等時（
a[i-1] == b[j-1]），代表我們成功配對到了一個新元素，這個元素可以加進 LCS 裡面，所以長度會是v[i-1][j-1] + 1。 - 如果不相等，代表這兩個元素不可能同時出現在當前的 LCS 結尾中，我們就取「捨棄陣列一當前元素（
v[i-1][j]）」或是「捨棄陣列二當前元素（v[i][j-1]）」兩者中的最大值，來繼承之前配對好的結果。
利用上述 DP 表把所有長度算出來後，v[n][m] 就是最長長度。
接著是求實際內容：我們從 DP 表的右下角 (n, m) 開始往回走。
- 如果這兩格的值相等（
a[i-1] == b[j-1]），就代表這個數字是當初成功配對並被加進子序列的，我們把它存進解答陣列裡面，然後往左上方走（i--,j--）。 - 如果不相等，就代表這一步的值是從上方或左方繼承過來的。我們就看是上面
v[i-1][j]比較大，還是左邊v[i][j-1]比較大，往數字比較大（當初繼承來源）的那個方向退回去即可。
最後因為我們是從後往前找的，答案陣列印出來之前要記得先反轉過來。
程式碼#
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define INF LONG_LONG_MAX/1000
#define WA() cin.tie(0)->sync_with_stdio(0)
#define all(x) (x).begin(), (x).end()
#define int long long
#define PII pair<int, int>
signed main() { WA();
int n, m; cin >> n >> m;
// 讀取兩個陣列
vector<int> a(n), b(m);
for (auto &i : a) cin >> i;
for (auto &i : b) cin >> i;
// v[i][j] 代表陣列 a 的前 i 個與陣列 b 的前 j 個元素的 LCS 長度
vector<vector<int>> v(n+1, vector<int>(m+1));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
// 如果遇到相同的元素，LCS 長度 +1
if (a[i-1] == b[j-1]) v[i][j] = v[i-1][j-1] + 1;
// 如果不同，則繼承包含該元素之前的最長長度
else v[i][j] = max(v[i-1][j], v[i][j-1]);
}
}
int i = n, j = m;
vector<int> ans;
// 從右下角往回追溯找出實際的子序列
while (i && j) {
// 如果該元素的組成是因為 a[i-1] 與 b[j-1] 匹配
if (a[i-1] == b[j-1]) {
// 加入答案中，然後雙雙往左上退一格
ans.pb(a[i-1]);
i--; j--;
}
// 反之，如果是因為捨棄 a 的當前元素而繼承而來，就往上退
else if (v[i-1][j] > v[i][j-1]) {
i--;
}
// 如果是因為捨棄 b 的當前元素而繼承而來，就往左退
else {
j--;
}
}
// 輸出最長子序列長度
cout << v[n][m] << '\n';
// 因為是從後往前找的，要把結果反轉回來再印出
for (auto &i : vector<int>(ans.rbegin(), ans.rend())) cout << i << ' ';
}
