最长回文子序列

区间 DP 经典题：区间两端相等时向内缩，不等时取左右子区间最大值。

#resource / algorithm #type / snippet #status / growing #source / leetcode #algo / dp

[!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];
};