【刷题题解】最长回文子序列

给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。

子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列

这道题，一眼动态规划，但是即使动起来也规划不了一点😅

好，这道题，我们可以这样子思考，先把视线聚焦在单个字符上，单个字符是s【i】就是一个回文字符串，所以，在此基础上，我们去扩展他的左右两边，如果s【i-1】==s【i+1】,那么回文字符串的长度加上这两个元素的长度2（即加2），否则，当前字符串的最长回文子字符串长度为max（包含左边界的最长字串长度，包含右边界的最长字符串）

大致思路就是这样子，我们用程序来拆分。

对于字符串 s，设 dp[i][j] 表示子串 s[i...j] 中最长回文子序列的长度。我们想要计算的最终结果是 dp[0][n-1]，其中 n 是字符串 s 的长度。

• 初始化：对于任何字符串，如果取长度为 1，即 i == j，那么最长回文子序列的长度就是 1，因为每个单独的字符都是一个回文序列。所以，dp[i][i] = 1 对所有 0 <= i < n。

• 状态转移方程：

  • 如果 s[i] == s[j]，那么我们找到了一对匹配的字符，可以在 s[i+1...j-1] 的基础上增加 2，即 dp[i][j] = dp[i+1][j-1] + 2。
  • 如果 s[i] != s[j]，那么最长回文子序列要么在 s[i+1...j] 中，要么在 s[i...j-1] 中，所以 dp[i][j] = max(dp[i+1][j], dp[i][j-1])。

• 填表顺序：由于计算 dp[i][j] 需要知道 dp[i+1][j-1]、dp[i+1][j] 和 dp[i][j-1] 的值，因此我们需要从底部开始填表，即从 i = n-1 开始向 i = 0 遍历，同时 j 从 i 开始向 n-1 遍历。

首先，通过Array.from和箭头函数初始化一个二维数组dp，然后按照状态转移方程填充这个数组。最后，返回dp[0][n - 1]的值作为整个字符串s的最长回文子序列长度。

function longestPalindromeSubseq(s) {
    const n = s.length;
    const dp = new Array(n).fill(0).map(() => new Array(n).fill(0));

    // 初始化，单个字符的情况
    for (let i = 0; i < n; i++) {
        dp[i][i] = 1;
    }

    // 填表
    for (let i = n - 2; i >= 0; i--) { // 从倒数第二行开始向上
        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]; // 返回整个字符串的最长回文子序列长度
}

我看有人提出将字符串翻转，然后求两个字符串的最长公共子序列就可以了。

这个思路是基于：字符串的最长回文子序列与其翻转后字符串的最长公共子序列（Longest Common Subsequence, LCS）长度相同。这是因为回文子序列在原字符串中的顺序和在翻转字符串中的顺序是相反的，而LCS正是寻找这样的序列。

思路分析

1. 翻转字符串：首先，得到原字符串s的翻转字符串reverseS。
2. 求最长公共子序列（LCS）：然后，求原字符串s和翻转字符串reverseS的最长公共子序列的长度。这个长度即为原字符串的最长回文子序列的长度。

动态规划求LCS

对于字符串s和它的翻转字符串reverseS，设dp[i][j]表示s[0...i-1]和reverseS[0...j-1]的最长公共子序列的长度。状态转移方程如下：

• 如果s[i-1] == reverseS[j-1]，那么dp[i][j] = dp[i-1][j-1] + 1；
• 否则，dp[i][j] = max(dp[i-1][j], dp[i][j-1])。

function longestPalindromeSubseq(s) {
    const n = s.length;
    const reverseS = s.split('').reverse().join('');
    const dp = new Array(n).fill(0).map(() => new Array(n).fill(0));

    for (let i = 1; i <= n; i++) {
        for (let j = 1; j <= n; j++) {
            if (s[i - 1] === reverseS[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }

    return dp[n][n]; // 返回整个字符串的最长回文子序列长度
}