最长回文子序列

在了解最长回文子序列之前，我们应该先了解“什么是子序列”。子序列是通过从序列中删除一些元素而不改变其余元素的顺序而获得的序列。

这里我们需要在给定的字符串中找到最长回文子序列。让我们通过一些例子来理解。

示例 1

输入字符串："a d b b c a"

最长回文子序列是 "a b b a"。子序列的长度是 4。

示例 2

输入字符串："p q r d r p d"

最长回文子序列是 "p r d r p"。子序列的长度是 5。

示例 3

输入字符串："p q r r q p"

最长回文子序列是 "p q r r q p"。子序列的长度是 6。

为了解决这个问题，我们将使用动态规划。这里我们使用记忆化矩阵。

假设给定以下字符串

输入字符串："a g b d b a"。 这里，我们考虑一个与字符串长度相同的矩阵。字符串的长度是 6，所以我们考虑一个 6*6 的矩阵。字符 'a', 'g', 'b', 'd', 'b', 'a' 的索引分别为 0, 1, 2, 3, 4, 5。

首先，我们考虑长度等于 1，即 l = 1。这意味着我们一次考虑单个字符。如果我们考虑单个字符，那么最长回文子序列的长度也等于 1。

现在我们考虑字符串长度为 2。这意味着我们一次考虑两个字符。首先，我们考虑 "a g" 作为字符串。由于两个字符不同，所以最长回文子序列的长度为 1，如下所示

现在我们考虑另一个字符串 "gb"。这意味着我们一次考虑两个字符。由于两个字符不同，所以最长回文子序列的长度为 1，如下所示

现在我们考虑另一个字符串 "bd"。这意味着我们一次考虑两个字符。由于两个字符不同，所以最长回文子序列的长度为 1，如下所示

现在我们考虑另一个字符串 "db"。这意味着我们一次考虑两个字符。由于两个字符不同，所以最长回文子序列的长度为 1，如下所示

现在我们考虑另一个字符串 "ba"。这意味着我们一次考虑两个字符。由于两个字符不同，所以最长回文子序列的长度为 1，如下所示

考虑字符串长度为 3，即 "a g b"。这意味着我们一次考虑三个字符。由于字符串的第一个字符和最后一个字符不同，所以我们考虑 "ag" 或 "gb"。 "ag" 和 "gb" 的长度都是 1，所以我们在 S[1][2] 处放置 1，如下所示

考虑字符串为 "g b d"。这意味着我们一次考虑三个字符。由于字符串的第一个字符和最后一个字符不同，所以我们考虑 "gb" 或 "bd"。 "gb" 和 "bd" 的长度都是 1，所以我们在 S[1][3] 处放置 1，如下所示

考虑字符串为 "b d b"。这意味着我们一次考虑三个字符。由于字符串的第一个字符和最后一个字符相同，所以最大回文子序列的长度等于 (2 + 1)，即 3。我们在 S[1][4] 处放置 3，如下所示

考虑字符串为 "d b a"。这意味着我们一次考虑三个字符。由于字符串的第一个字符和最后一个字符不同，所以我们考虑 "db" 或 "ba"。 "db" 和 "ba" 的长度都是 1，所以我们在 S[1][5] 处放置 1，如下所示

现在我们有长度 l=4。我们考虑索引从 0 到 3。考虑字符串为 "a g b d"。这意味着我们一次考虑四个字符。由于字符串的第一个字符和最后一个字符不同，所以我们取三个字符的字符串，要么是 "a g b" 要么是 "g b d"。 "a g b" 和 "g b d" 的长度相同，即 1，所以我们在 S[0][3] 处放置 1。

考虑索引从 1 到 4。考虑字符串为 "g b d b"。这意味着我们一次考虑四个字符。由于字符串的第一个字符和最后一个字符不同，所以我们一次取三个字符的字符串，要么是 "g b d" 要么是 "b d b"。字符串 "b d b" 的回文子序列的最大长度是 3，所以我们在 S[1][4] 处加 3。

考虑索引从 2 到 5。考虑字符串为 "b d b a"。这意味着我们一次考虑四个字符。由于字符串的第一个字符和最后一个字符不同，所以考虑三个字符的字符串，要么是 "b d b" 要么是 "d b a"。字符串 "b d b" 的回文子序列的最大长度是 3，所以我们在 S[2][5] 处加 3，如下所示

现在我们有长度 l = 5。考虑索引从 0 到 4。考虑字符串为 "a g b d b"。这意味着我们一次取五个字符。由于字符串的第一个字符和最后一个字符不同，所以我们考虑四个字符的字符串，要么是 "a g b d" 要么是 "g b d b"。字符串 "g b d b" 的回文子序列的长度是 3，这是最大的，所以我们在 S[0][4] 处加 3，如下所示

考虑索引从 1 到 5。考虑字符串为 "g b d b a"。这意味着我们一次取五个字符。由于字符串的第一个字符和最后一个字符不同，所以我们考虑四个字符的字符串，要么是 "g b d b" 要么是 "b d b a"。两个字符串的长度都是 3，我们在 S[1][5] 处加 3，如下所示

现在我们有长度 l = 6。考虑索引从 0 到 5。考虑字符串为 "a g b d b a"。这意味着我们一次取六个字符。由于字符串的第一个字符和最后一个字符相同，所以 S[0][5] 的值等于 2 加上 S[1][4] 的值，即 (2+3) 等于 5，如下所示

正如我们可以在上表中观察到的，考虑字符串 "a g b d b a" 产生了回文子序列的长度，即 5。由于长度 5 来自长度为 3 的字符串 "g b d b"，长度 3 来自长度等于 3 的字符串 "b d b"，长度 3 来自长度为 1 的字符串 "d"，如下所示

现在我们将找到字符串。由于 5 来自 3；因此，索引 0 和 5 的字符将包含在字符串中，即 'a'，如下所示

S: a a

由于 3 来自长度 3；因此，索引 2 和 4 的字符将包含在字符串中，如下所示

S: a b b a

由于长度 3 来自 1；因此，索引 3 的字符，即 'd' 将包含在字符串中，如下所示

S: a b d b a

在这个问题中，回文子序列是 "a b d b a"，它具有最长回文子序列（5）。

回文子序列算法

C 语言实现

输出