最長的迴文子序列

Created: November-22, 2018

給出一個字串，它的最長的迴文子序列（LPS）是什麼？我們來一個字串 agbdba 。該字串的 LPS 是長度為 5 的 abdba 。請記住，因為我們正在尋找子序列，所以字元不需要在原始字串中連續。序列的最長迴文子字串將是長度為 3 的 bdb 。但我們將集中精力於此處的後續序列。我們將使用動態程式設計來解決這個問題。 ** ** **** **** **

首先，我們將採用與原始序列相同維度的 2D 陣列。對於我們的例子：S = "agbdba"，我們將採用 dp [6] [6] 陣列。這裡， dp [i] [j] 表示如果我們考慮從 s [i] 到 s [j] 的字元，我們可以製作的 LPS 的長度。例如。如果我們的字串是 aa ， dp [0] [1] 將儲存 2 。現在我們將考慮不同長度的字串，並找出我們可以用它做出的最長可能長度。

長度= 1 ：
這裡，我們一次只考慮 1 個字元。所以如果我們有一個長度為 1 的字串，我們可以擁有什麼樣的 LPS？當然答案是 1 。如何存放？ dp [i] [j] 其中 i 等於 j 表示長度為 1 的字串。所以我們將設定 dp [0] [0] ， dp [1] [1] ， dp [2] [2] ， dp [3] [3] ， dp [4] [4] ， dp [5] [ 5] 到 1 。我們的陣列看起來像：

+---+---+---+---+---+---+---+
|   | 0 | 1 | 2 | 3 | 4 | 5 |
+---+---+---+---+---+---+---+
| `0` | 1 |   |   |   |   |   |
+---+---+---+---+---+---+---+
| `1` |   | 1 |   |   |   |   |
+---+---+---+---+---+---+---+
| `2` |   |   | 1 |   |   |   |
+---+---+---+---+---+---+---+
| `3` |   |   |   | 1 |   |   |
+---+---+---+---+---+---+---+
| `4` |   |   |   |   | 1 |   |
+---+---+---+---+---+---+---+
| `5` |   |   |   |   |   | 1 |
+---+---+---+---+---+---+---+

長度= 2 ：
這次我們將考慮長度為 2 的字串。現在考慮長度為 2 的字串，當且僅當字串的兩個字元相同時，LPS 的最大長度可以是 2 。所以我們的策略是：

j := i + Length - 1
if s[i] is equal to s[j]
    dp[i][j] := 2
else
    dp[i][j] := 1

如果我們按照 Length = 2 的策略填充我們的陣列，我們將獲得：

+---+---+---+---+---+---+---+
|   | 0 | 1 | 2 | 3 | 4 | 5 |
+---+---+---+---+---+---+---+
| `0` | 1 | 1 |   |   |   |   |
+---+---+---+---+---+---+---+
| `1` |   | 1 | 1 |   |   |   |
+---+---+---+---+---+---+---+
| `2` |   |   | 1 | 1 |   |   |
+---+---+---+---+---+---+---+
| `3` |   |   |   | 1 | 1 |   |
+---+---+---+---+---+---+---+
| `4` |   |   |   |   | 1 | 1 |
+---+---+---+---+---+---+---+
| `5` |   |   |   |   |   | 1 |
+---+---+---+---+---+---+---+

長度= 3 ：
現在我們一次檢視 3 個字元作為原始字串。從現在起 LPS 我們可以從我們的字串中確定：

如果第一個和最後一個字元匹配，我們將至少有兩個專案，如果我們排除第一個和最後一個字元，我們可以從中製作 LPS +，我們可以從剩餘字串中做到最好。
如果第一個和最後一個字元不匹配，我們可以製作的 LPS 將來自排除我們已經計算過的第一個字元或最後一個字元。

總結一下，

j := i + Length - 1
if s[i] is equal to s[j]
    dp[i][j] := 2 + dp[i+1][j-1]
else
    dp[i][j] := max(dp[i+1][j], dp[i][j-1])
end if

如果我們將長度 = 3 的 dp 陣列填充到 Length = 6 ，我們將得到： **** **** **** ****

+---+---+---+---+---+---+---+
|   | 0 | 1 | 2 | 3 | 4 | 5 |
+---+---+---+---+---+---+---+
| `0` | 1 | 1 | 1 | 1 | 3 | 5 |
+---+---+---+---+---+---+---+
| `1` |   | 1 | 1 | 1 | 3 | 3 |
+---+---+---+---+---+---+---+
| `2` |   |   | 1 | 1 | 3 | 3 |
+---+---+---+---+---+---+---+
| `3` |   |   |   | 1 | 1 | 1 |
+---+---+---+---+---+---+---+
| `4` |   |   |   |   | 1 | 1 |
+---+---+---+---+---+---+---+
| `5` |   |   |   |   |   | 1 |
+---+---+---+---+---+---+---+

這是我們所需的 dp 陣列， dp [0] [5] 將包含 LPS 的長度。我們的程式如下：

Procedure LPSLength(S):
n := S.length
dp[n][n]
for i from 0 to n
    dp[i][i] := 1
end for
for i from 0 to (n-2)
    if S[i] := S[i+1]
        dp[i][i+1] := 2
    else
        dp[i][i+1] := 1
    end if
end for
Length := 3
while Length <= n
    for i from 0 to (n - Length)
        j := i + Length - 1
        if S[i] is equal to s[j]
            dp[i][j] := 2 + dp[i+1][j-1]
        else
            dp[i][j] := max(dp[i+1][j], dp[i][j-1])
        end if
    end for
Length := Length + 1
end while
Return dp[0][n-1]

該演算法的時間複雜度為 O(n²)，其中 n 是給定字串的長度。最長的迴文序列子問題與最長公共子序列密切相關。如果我們將第二個字串作為第一個字串的反向並計算長度並列印結果，那將是給定字串的最長迴文子序列。該演算法的複雜性也很明顯。