最長回文子序列

最長回文子序列（Longest Palindromic Subsequence, LPS）是一個在字元串中尋找最長的回文子序列的問題。回文子序列是一系列字元，它們從字元串的開始到結束順序與其相反方向上的順序相同，例如 "ABBA"、"BBC" 和 "ABBCBBA" 都是回文子序列。

最長回文子序列問題可以通過動態規劃（Dynamic Programming）來解決。動態規劃算法的基本思想是：將大問題分解為小問題來解決，從而避免重複計算，提高效率。

以下是動態規劃算法來解決最長回文子序列問題的步驟：

  1. 定義狀態：設 dp[i][j] 表示字元串中前 i 個字元和前 j 個字元的最長回文子序列的長度。

  2. 狀態轉移方程：如果字元串的第 i 個字元和第 j 個字元相同，那麼 dp[i][j] 等於 dp[i-1][j-1] 加上 1（表示第 i 個字元和第 j 個字元本身），否則 dp[i][j] 等於 max(dp[i-1][j], dp[i][j-1])。

  3. 初始化：dp[0][0] = 1（表示空字元串是一個回文子序列），其他 dp[i][j] 初始化為 0。

  4. 通過狀態轉移方程計算出 dp[n-1][n-1]（其中 n 是字元串的長度），最長回文子序列的長度就是 dp[n-1][n-1]。

以下是一個簡單的Python實現：

def lps(s):
    n = len(s)
    dp = [[0] * (n + 1) for _ in range(n + 1)]

    for i in range(n):
        dp[i][i] = 1

    for i in range(n - 1, 0, -1):
        for j in range(i, n):
            if s[i] == s[j]:
                dp[i][j] = dp[i + 1][j - 1] + 1

    return dp[0][n - 1]

# 測試
s = "abba"
print(lps(s))  # 輸出最長回文子序列的長度

在這個實現中，lps 函式接受一個字元串 s 作為輸入，並返回 s 的最長回文子序列的長度。

請注意，這個算法的時間複雜度和空間複雜度都是 O(n^2)，其中 n 是字元串的長度。對於長字元串，這個算法可能會很慢。存在更高效的算法，例如 Manacher 算法，可以在 O(n) 時間內解決最長回文子序列問題，但是 Manacher 算法的實現相對複雜。