leetcode 516. 最长回文子序列(JAVA)题解

LeetCode第516题“最长回文子序列”的问题描述如下：给定一个字符串s，找到该字符串的最长回文子序列的长度。回文子序列是指一个序列，从前往后和从后往前读是一样的。不同于回文串，回文子序列不要求字符连续。

问题分析

比如，给定字符串s= "bbbab"，其最长回文子序列为"bbbb"，长度为4。为了求解这个问题，我们可以用动态规划的方法来实现。这样可以有效地减少重复计算，从而提高算法的效率。

动态规划思路

1. 状态定义：设dp[i][j]表示字符串s从索引i到索引j之间的最长回文子序列的长度。

2. 状态转移方程：

3. 如果s[i] == s[j]，那么dp[i][j] = dp[i + 1][j - 1] + 2，因为s[i]和s[j]可以组成回文序列。

4. 如果s[i] != s[j]，那么我们需要选择不包含s[i]或不包含s[j]的子序列，即dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])。

5. 初始状态：所有单个字符的回文子序列长度为1，即dp[i][i] = 1。

6. 计算顺序：我们需要从短到长填充dp数组，因此我们可以先处理较小的子问题，再逐步解决更大的子问题。

代码实现

以下是实现上述思路的Java代码：

public class LongestPalindromeSubseq {
    public int longestPalindromeSubseq(String s) {
        int n = s.length();
        // dp[i][j]表示s从i到j的最长回文子序列的长度
        int[][] dp = new int[n][n];

        // 初始化：每个单字符的回文子序列长度为1
        for (int i = 0; i < n; i++) {
            dp[i][i] = 1;
        }

        // 从下往上填充dp数组
        for (int length = 2; length <= n; length++) { // length为子串的长度
            for (int i = 0; i <= n - length; i++) {
                int j = i + length - 1; // j是当前子串的结束索引
                if (s.charAt(i) == s.charAt(j)) {
                    dp[i][j] = dp[i + 1][j - 1] + 2; // 端点字符相同
                } else {
                    dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]); // 端点字符不同
                }
            }
        }

        // 返回s从0到n-1的最长回文子序列长度
        return dp[0][n - 1];
    }

    public static void main(String[] args) {
        LongestPalindromeSubseq solution = new LongestPalindromeSubseq();
        String s = "bbbab";
        int length = solution.longestPalindromeSubseq(s);
        System.out.println("字符串 \"" + s + "\" 的最长回文子序列长度为: " + length); // 输出4
    }
}

复杂度分析

• 时间复杂度: O(n^2)，因为我们需要填充n x n的dp数组。
• 空间复杂度: O(n^2)，存储状态数组，若只用到上一步的结果，可以减少空间复杂度到O(n)。

总结

通过动态规划的方法，我们成功地找到了字符串s的最长回文子序列。这个过程展示了如何利用状态转移方程将复杂问题转化为子问题，从而一步步求解出最终的答案。