什麼是最長公共子序列

最長公共子序列（Longest Common Subsequence, LCS）是一個在兩組或多組序列中找到最長的公共子序列的問題。這裡的「子序列」是指一個序列中的一些元素，它們保持原有的相對順序。例如，序列 "ABCDGH" 的一個子序列是 "ABCDEF"，因為它包含了 "ABCDGH" 中的所有字母，並且保持了它們的順序。但是 "ABDGH" 不是一個子序列，因為 "C" 不在其中。

最長公共子序列問題是在給定兩組或多組序列的情況下，找到它們共有的最長子序列。例如，給序列 "ABCDGH" 和 "AEDFHR"，它們的最長公共子序列是 "ADFH"。

最長公共子序列問題在許多領域都有應用，例如生物信息學中的序列比對、軟件版本控制系統中的變更追蹤、機器翻譯中的對齊文本等。

解決最長公共子序列問題可以使用 Dynamic Programming（動態規劃）的方法。動態規劃的思路是將大問題分解為小問題來解決，並且記錄已經解決的小問題的答案，以便重複使用它們來解決更大的問題。在 LCS 問題中，我們可以使用一個二維數組來存儲已經解決的小問題，從而避免重複計算。