使用动态规划求解最长回文子序列问题

1. 概述

本文将讲解最长回文子序列（Longest Palindromic Subsequence）问题的动态规划解法。

我们会先给出问题定义和基本概念，然后通过几个示例帮助理解问题。接着，将介绍如何使用动态规划中的自顶向下（Top-Down）和自底向上（Bottom-Up）两种方式求解。

在开始之前，建议读者熟悉动态规划的基础知识。如果对相关概念不熟悉，可以先阅读《背包问题》或《最长递增子序列》等基础动态规划文章。

2. 定义

我们先明确几个关键术语：

子序列（Subsequence）：子序列是指从原序列中删除若干元素（可以为零）后形成的序列，但元素顺序保持不变。例如，bdf 是 abcdefg 的子序列；但 abd 不是 baed 的子序列，因为改变了元素顺序。
回文（Palindrome）：回文序列是指正序和逆序读都一样的序列。例如 abcba、byzzyb 是回文，而 abca 不是。

因此，本题的目标是：给定一个字符序列，找出其最长回文子序列的长度。

3. 示例

下表展示了几个字符串及其对应的最长回文子序列：

示例	原始字符串	最长回文子序列	长度	备注
1	`abcdecac`	`acdca` 或 `aceca`	5	多个答案，长度相同
2	`abcdef`	`a`（或任意单个字符）	1	单个字符即为回文
3	`xyzazyx`	`xyzazyx`	7	整个字符串本身就是回文
4	`aedbceba`	`aebbea`	6	还有其他回文子序列，但长度更短

⚠️ 注意：我们只关心最长回文子序列的长度，而不是具体有哪些子序列。

4. 动态规划解法

为了使用动态规划解决这个问题，我们需要将问题拆解为子问题，并找出状态转移方式。

我们定义状态 dp[L][R] 表示原字符串中从索引 L 到 R 的子序列中，最长回文子序列的长度。

4.1 自顶向下（Top-Down）解法

这是递归加记忆化的做法，通常更容易理解。

核心思路如下：

如果 L > R，返回 0（空区间）。
如果 L == R，返回 1（单个字符是回文）。
如果 s[L] == s[R]，则 dp[L][R] = 2 + dp[L+1][R-1]。
否则，dp[L][R] = max(dp[L+1][R], dp[L][R-1])。

✅ Java 示例代码如下：

public class LongestPalindromicSubsequence {
    private static int[][] dp;
    private static char[] s;

    public static int solve(int L, int R) {
        if (L > R) return 0;
        if (L == R) return 1;
        if (dp[L][R] != -1) return dp[L][R];

        if (s[L] == s[R]) {
            dp[L][R] = 2 + solve(L + 1, R - 1);
        } else {
            int moveLeft = solve(L + 1, R);
            int moveRight = solve(L, R - 1);
            dp[L][R] = Math.max(moveLeft, moveRight);
        }

        return dp[L][R];
    }

    public static void main(String[] args) {
        String input = "aedbceba";
        s = input.toCharArray();
        int n = s.length;
        dp = new int[n][n];
        for (int i = 0; i < n; i++) {
            Arrays.fill(dp[i], -1);
        }
        System.out.println("最长回文子序列长度: " + solve(0, n - 1));
    }
}

时间复杂度： ✅ O(n^2)，其中 n 是字符串长度。

4.2 自底向上（Bottom-Up）解法

这种解法通过填表的方式，从小问题逐步构建到最终问题的解。

我们依然使用 dp[L][R] 表示从 L 到 R 的最长回文子序列长度。

填表顺序：

长度为 1 的子串长度为 1。
从长度为 2 开始，逐步增加到 n。
对每个长度，枚举所有可能的左边界 L，并计算右边界 R = L + len - 1。

✅ Java 示例代码如下：

public class LongestPalindromicSubsequenceBottomUp {
    public static int longestPalindromeSubseq(String s) {
        int n = s.length();
        int[][] dp = new int[n][n];

        // 单个字符长度为1
        for (int i = 0; i < n; i++) {
            dp[i][i] = 1;
        }

        // 从长度2开始填表
        for (int len = 2; len <= n; len++) {
            for (int L = 0; L <= n - len; L++) {
                int R = L + len - 1;
                if (s.charAt(L) == s.charAt(R)) {
                    dp[L][R] = 2 + dp[L + 1][R - 1];
                } else {
                    dp[L][R] = Math.max(dp[L + 1][R], dp[L][R - 1]);
                }
            }
        }

        return dp[0][n - 1];
    }

    public static void main(String[] args) {
        String input = "abcdecac";
        System.out.println("最长回文子序列长度: " + longestPalindromeSubseq(input));
    }
}

时间复杂度： ✅ O(n^2)，空间复杂度也为 O(n^2)。

5. 总结

本文讲解了最长回文子序列问题的定义和示例，并给出了两种动态规划解法：

方法	时间复杂度	空间复杂度	优点	缺点
自顶向下（Top-Down）	`O(n^2)`	`O(n^2)`	易于理解和实现	递归可能导致栈溢出（大输入时）
自底向上（Bottom-Up）	`O(n^2)`	`O(n^2)`	高效稳定	理解难度稍高

两种方法各有优劣，可以根据实际场景选择使用。如果输入较大，推荐使用 Bottom-Up 方法以避免递归栈溢出问题。

Persistence

REST

Security