[!info] related notes 算法面试题型 MOC 动态规划 区间 DP 与状态机 DP

最长回文子串

题目链接：https://leetcode.cn/problems/longest-palindromic-substring/

题意

给你一个字符串 s，返回其中最长的回文子串。

为什么是区间 DP

一个子串 s[i...j] 是否为回文，取决于：

• s[i] 和 s[j] 是否相等
• 内部子串 s[i + 1...j - 1] 是否为回文

这就是典型的区间依赖。

状态

dp[i][j] 表示 s[i...j] 是否为回文串。

转移

dp[i][j] = (s[i] === s[j]) && (j - i <= 1 || dp[i + 1][j - 1])

遍历顺序

因为依赖更短区间 dp[i + 1][j - 1]，所以要让：

• i 从大到小
• j 从小到大

或者按区间长度从小到大。

样例

s = "babad"

• 回文子串有：b、a、d、bab、aba
• 最长长度是 3

答案可以是 "bab" 或 "aba"。

JavaScript

var longestPalindrome = function(s) {
    const n = s.length;
    const dp = Array.from({ length: n }, () => new Array(n).fill(false));
    let start = 0;
    let maxLen = 1;

    for (let i = n - 1; i >= 0; i--) {
        for (let j = i; j < n; j++) {
            if (s[i] === s[j] && (j - i <= 1 || dp[i + 1][j - 1])) {
                dp[i][j] = true;
                if (j - i + 1 > maxLen) {
                    maxLen = j - i + 1;
                    start = i;
                }
            }
        }
    }

    return s.slice(start, start + maxLen);
};

易错点

• 长度为 1 和 2 的区间要单独考虑：这就是 j - i <= 1
• 遍历顺序错了就会读到还没算出的 dp[i + 1][j - 1]