最长回文子序列（Longest Palindromic Subsequence）问题

字数 1936 2025-12-13 15:29:40

最长回文子序列（Longest Palindromic Subsequence）问题

问题描述
最长回文子序列（Longest Palindromic Subsequence，LPS）是给定一个字符串，找出其中最长的回文子序列的长度。子序列不要求连续，但必须保持字符的相对顺序。回文是指正读反读都相同的字符串。

例如，字符串 "bbabcbcab" 的最长回文子序列是 "babcbab"（长度为7）或 "bacbcab"（长度为7）。注意：子序列不同于子串，子串要求连续。

解题思路
这是一个经典的动态规划问题。我们可以从字符串的两端向中间推导，或者从中间向两端扩展。下面我使用自底向上的动态规划方法，构建一个二维DP表。

动态规划定义
设 dp[i][j] 表示字符串 s 从索引 i 到 j（包含两端）的子串中最长回文子序列的长度。

目标：求 dp[0][n-1]，其中 n 是字符串长度。
基础情况：
- 当 i == j 时，只有一个字符，它本身就是一个回文序列，所以 dp[i][j] = 1。
- 当 i > j 时，空子串，dp[i][j] = 0（通常不会用到，但为了方便定义）。

状态转移方程
考虑子串 s[i..j]：

如果 s[i] == s[j]，那么这两个字符可以成为回文序列的一部分。我们取内部子串 s[i+1..j-1] 的最长回文子序列，并加上这两个字符，所以 dp[i][j] = dp[i+1][j-1] + 2。
如果 s[i] != s[j]，那么这两个字符不能同时作为回文序列的两端。我们只能从 s[i+1..j] 或 s[i..j-1] 中选择更长的回文子序列，即 dp[i][j] = max(dp[i+1][j], dp[i][j-1])。

计算顺序
因为 dp[i][j] 依赖于 dp[i+1][j-1]（左下角）、dp[i+1][j]（正下方）和 dp[i][j-1]（正左方），所以我们从底向上、从左到右计算。即先计算较短的子串，再计算较长的子串。

示例推导
以字符串 "bbabcbcab" 为例，长度为9。我们构建一个 9×9 的DP表，只使用上三角部分（因为 i <= j）。

初始化对角线：所有 dp[i][i] = 1。
考虑长度为2的子串（即 j = i+1）：
- 比如子串 "bb"：s[0]==s[1]，所以 dp[0][1] = dp[1][0] + 2，但 i>j 时我们视为0，所以 dp[0][1] = 0 + 2 = 2。
- 其他类似计算。
长度递增，直到整个字符串。

为了更清晰，我手动计算前几步：

dp[0][1]：s[0]='b', s[1]='b'，相等，所以 dp[0][1] = dp[1][0] + 2 = 0 + 2 = 2。
dp[1][2]：s[1]='b', s[2]='a'，不等，所以 dp[1][2] = max(dp[2][2], dp[1][1]) = max(1, 1) = 1。

继续这个过程，最终 dp[0][8] 就是结果。

算法实现步骤

输入字符串 s，长度 n。
创建二维数组 dp[n][n]，初始化为0。
将对角线 dp[i][i] 设为1。
从子串长度 len = 2 到 n 循环：
- 对于每个起始索引 i 从 0 到 n - len：
  - 计算结束索引 j = i + len - 1。
  - 如果 s[i] == s[j]：
    - 如果 len == 2，dp[i][j] = 2（因为内部为空，相当于 dp[i+1][j-1] = 0）。
    - 否则，dp[i][j] = dp[i+1][j-1] + 2。
  - 否则，dp[i][j] = max(dp[i+1][j], dp[i][j-1])。
返回 dp[0][n-1]。

复杂度分析

时间复杂度：O(n²)，因为要填充一个 n×n 的DP表。
空间复杂度：O(n²)，用于存储DP表。可以优化到 O(n) 只存储两行，但实现稍复杂。

扩展：如何输出最长回文子序列
除了长度，有时需要输出该子序列。我们可以在DP过程中记录决策方向（来自左上、左或下），然后从 dp[0][n-1] 反向构建字符串。

总结
最长回文子序列问题通过动态规划将问题分解为重叠子问题，利用回文的对称性质，逐步构建出全局最优解。掌握这个问题的关键在于理解状态定义和转移方程，以及如何正确地遍历子串长度。

最长回文子序列（Longest Palindromic Subsequence）问题问题描述最长回文子序列（Longest Palindromic Subsequence，LPS）是给定一个字符串，找出其中最长的回文子序列的长度。子序列不要求连续，但必须保持字符的相对顺序。回文是指正读反读都相同的字符串。例如，字符串 "bbabcbcab" 的最长回文子序列是 "babcbab"（长度为7）或 "bacbcab"（长度为7）。注意：子序列不同于子串，子串要求连续。解题思路这是一个经典的动态规划问题。我们可以从字符串的两端向中间推导，或者从中间向两端扩展。下面我使用自底向上的动态规划方法，构建一个二维DP表。动态规划定义设 dp[i][j] 表示字符串 s 从索引 i 到 j （包含两端）的子串中最长回文子序列的长度。目标：求 dp[0][n-1] ，其中 n 是字符串长度。基础情况：当 i == j 时，只有一个字符，它本身就是一个回文序列，所以 dp[i][j] = 1 。当 i > j 时，空子串， dp[i][j] = 0 （通常不会用到，但为了方便定义）。状态转移方程考虑子串 s[i..j] ：如果 s[i] == s[j] ，那么这两个字符可以成为回文序列的一部分。我们取内部子串 s[i+1..j-1] 的最长回文子序列，并加上这两个字符，所以 dp[i][j] = dp[i+1][j-1] + 2 。如果 s[i] != s[j] ，那么这两个字符不能同时作为回文序列的两端。我们只能从 s[i+1..j] 或 s[i..j-1] 中选择更长的回文子序列，即 dp[i][j] = max(dp[i+1][j], dp[i][j-1]) 。计算顺序因为 dp[i][j] 依赖于 dp[i+1][j-1] （左下角）、 dp[i+1][j] （正下方）和 dp[i][j-1] （正左方），所以我们从底向上、从左到右计算。即先计算较短的子串，再计算较长的子串。示例推导以字符串 "bbabcbcab" 为例，长度为9。我们构建一个 9×9 的DP表，只使用上三角部分（因为 i <= j ）。初始化对角线：所有 dp[i][i] = 1 。考虑长度为2的子串（即 j = i+1 ）：比如子串 "bb"： s[0]==s[1] ，所以 dp[0][1] = dp[1][0] + 2 ，但 i>j 时我们视为0，所以 dp[0][1] = 0 + 2 = 2 。其他类似计算。长度递增，直到整个字符串。为了更清晰，我手动计算前几步： dp[0][1] ： s[0]='b' , s[1]='b' ，相等，所以 dp[0][1] = dp[1][0] + 2 = 0 + 2 = 2 。 dp[1][2] ： s[1]='b' , s[2]='a' ，不等，所以 dp[1][2] = max(dp[2][2], dp[1][1]) = max(1, 1) = 1 。继续这个过程，最终 dp[0][8] 就是结果。算法实现步骤输入字符串 s ，长度 n 。创建二维数组 dp[n][n] ，初始化为0。将对角线 dp[i][i] 设为1。从子串长度 len = 2 到 n 循环：对于每个起始索引 i 从 0 到 n - len ：计算结束索引 j = i + len - 1 。如果 s[i] == s[j] ：如果 len == 2 ， dp[i][j] = 2 （因为内部为空，相当于 dp[i+1][j-1] = 0 ）。否则， dp[i][j] = dp[i+1][j-1] + 2 。否则， dp[i][j] = max(dp[i+1][j], dp[i][j-1]) 。返回 dp[0][n-1] 。复杂度分析时间复杂度：O(n²)，因为要填充一个 n×n 的DP表。空间复杂度：O(n²)，用于存储DP表。可以优化到 O(n) 只存储两行，但实现稍复杂。扩展：如何输出最长回文子序列除了长度，有时需要输出该子序列。我们可以在DP过程中记录决策方向（来自左上、左或下），然后从 dp[0][n-1] 反向构建字符串。总结最长回文子序列问题通过动态规划将问题分解为重叠子问题，利用回文的对称性质，逐步构建出全局最优解。掌握这个问题的关键在于理解状态定义和转移方程，以及如何正确地遍历子串长度。