[!info] related notes 动态规划 区间 DP 与状态机 DP 最长回文子串

最长回文子序列

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

状态

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

转移

• 如果 s[i] === s[j]：

dp[i][j] = dp[i + 1][j - 1] + 2

• 否则：

dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])

JavaScript

var longestPalindromeSubseq = function(s) {
    const n = s.length;
    const dp = Array.from({ length: n }, () => new Array(n).fill(0));

    for (let i = n - 1; i >= 0; i--) {
        dp[i][i] = 1;
        for (let j = i + 1; j < n; j++) {
            if (s[i] === s[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];
};