LeetCode 516. 最长回文子序列

Categories:

Tags:

题目描述
思路分析
1. 解法一：区间动态规划（推荐）
相似题目

题目描述

✅ 516. 最长回文子序列

思路分析

解法一：区间动态规划（推荐）

核心思路：

设 dp[i][j] 表示子串 s[i..j] 的最长回文子序列长度。

若 s[i] == s[j]，则 dp[i][j] = dp[i+1][j-1] + 2；否则取 dp[i+1][j] 与 dp[i][j-1] 的最大值。

需从短区间向长区间推进，i 逆序、j 正序填表。

复杂度分析：

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

空间复杂度：O(n^2)，使用二维 DP 表。

class Solution {
    public 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;
        }

        // 按区间长度递推
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i + 1; j < n; 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]);
                }
            }
        }

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

func longestPalindromeSubseq(s string) int {
    n := len(s)
    dp := make([][]int, n)
    for i := 0; i < n; i++ {
        dp[i] = make([]int, n)
        dp[i][i] = 1
    }

    // 按区间长度递推
    for i := n - 1; i >= 0; i-- {
        for j := i + 1; j < n; j++ {
            if s[i] == s[j] {
                dp[i][j] = dp[i+1][j-1] + 2
            } else {
                if dp[i+1][j] > dp[i][j-1] {
                    dp[i][j] = dp[i+1][j]
                } else {
                    dp[i][j] = dp[i][j-1]
                }
            }
        }
    }

    return dp[0][n-1]
}

相似题目

题目	难度	考察点
5. 最长回文子串	中等	区间 DP
647. 回文子串	中等	中心扩展
1312. 让字符串成为回文串的最少插入次数	困难	区间 DP
1143. 最长公共子序列	中等	序列 DP
583. 两个字符串的删除操作	中等	LCS 变形

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/66793237