最长的回文子序列

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 是给定字符串的长度。最长的回文序列子问题与最长公共子序列密切相关。如果我们将第二个字符串作为第一个字符串的反向并计算长度并打印结果，那将是给定字符串的最长回文子序列。该算法的复杂性也很明显。