即题目中提及的 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