即題目中提及的 Longest Common Subsequence。 也就是說，找到最長的 Sequence 使其為 s1 與 s2 的 Subsequence。 防一下雷… 故知此 Sequence 必為 s1 之 Subsequence，因此可窮舉 s1 之所有 Subsequence 來檢驗是否為 s2 之 Subsequence，記錄長度最長為何即可。 至於窮舉方式，反正 Subsequence 就是每個字選擇取與不取，因此共 2^n 種。 用遞迴去窮舉即可。 另外一個方法是使用動態規劃的方法。 考慮兩個序列 a, b 長度分別為 n, m，若兩者尾巴一樣，即 a[n] == b[m]， 可知此二序列之 LCS 必為 a, b 去尾後之 LCS 長度 +1。 若以 f(i, j) 代表 a 前 i 個字元及 b 前 i 個字元之 LCS， 則上述即為 f(n, m) = f(n-1, m-1) if a[n] == b[m] 若不相同呢？可知其 LCS 為拿掉 a[n] 或拿掉 b[m] 其中最大者， 因為其實這些情形加上 a[n] 或加上 b[m] 並不會影響 LCS 個數， 擇優錄取即可。故此情形即為： f(n, m) = max(f(n-1, m), f(n, m-1)) otherwise 可知邊界條件，若其中之一長度為 0，則 LCS 必為 0。 故得： f(n, m) = 0 if n == 0 || m == 0 至於實作方式有二，一為用兩層迴圈去跑 i, j， 順序無所謂，只要能確保跑到 i, j 時已跑過 (i-1, j), (i-1, j-1), (i, j-1) 即可。 另一為使用遞迴，但由於重覆運算量極大，如 (i, j) 可能被 (i+1, j), (i, j+1) 甚至 (i+1, j+1) 呼叫，可能會算很多次，那麼在它底下的就會被算更多次。 如果每一層都多算一兩次，那麼整體下來就很可怕了… 因此，必須記住哪些是計算過的；就不再計算。 可知 (i, j) 解答是固定的，不因其它外在條件而改變， 因此若是首次遇見，則遞迴求解之，並記錄此問題已被解開、以及答案為何； 下次再遇見，則直接告知答案即可，無須再算。 另有一方法是使用 Longest (Strictly) Increasing Subsequence (LIS) 來對 LCS 做極限優化，不過應該沒必要這樣，要講也更難講… 如果有興趣再私下問我好了。 貼心文末防雷。 --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.112.240.202