什麼是最長公共子序列問題

最長公共子序列（Longest Common Subsequence, LCS）問題是計算兩個或更多序列中共同出現的最長子序列的長度或實際序列。這裡的「子序列」是指一個序列中的一些元素，它們保持原序列的相對順序不變。例如，序列 "ABCDGH" 和 "AEDFH" 的最長公共子序列是 "ADFH"。

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

解決最長公共子序列問題可以使用 Dynamic Programming（動態規劃）的方法。基本思路是將問題分解為較小的子問題，並記錄這些子問題的答案，以避免重複計算。這樣可以有效地找到最長公共子序列，並且可以在 O(n^2) 的時間複雜度內解決，其中 n 是序列中最長的元素數。

有許多算法可以用來解決最長公共子序列問題，包括 LCS 算法、Smith-Waterman 算法和 Needleman-Wunsch 算法等。這些算法的選擇取決於序列的類型和應用場景。