1. 题目描述

给定一个字符串 s ，找到其中最长的回文子序列，并返回该序列的长度。可以假设 s 的最大长度为 1000 。

示例 1:

  1. 输入: "bbbab"
  2. 输出: 4
  3. 一个可能的最长回文子序列为 "bbbb"。

示例 2:

  1. 输入: "cbbd"
  2. 输出: 2
  3. 一个可能的最长回文子序列为 "bb"。

提示：

  • 1 <= s.length <= 1000
  • s 只包含小写英文字母

    2. 解题思路

    对于这种回文子串的问题，我们可以考虑能否使用动态规划来求解。

这里我们尝试使用动态规划来解答，初始化一个dp二维数组来保存子串的长度，dp[i][j]表示s中的第i个字符到第j个字符组成的子串中，最长的回文序列的长度。

下面最重要的就是找出状态转移方程：

  • 如果字符串s的第i个和第j个字符相同：f[i][j] = f[i + 1][j - 1] + 2
  • 如果字符串s的第i个和第j个字符不相同：f[i][j] = max(f[i + 1][j], f[i][j - 1])

这里需要注意遍历时的顺序，i是从最后一个字符开始遍历的，j是从i+1开始向后遍历，这样就能保证每个子问题都计算好了。最后只要返回dp[0][len-1]即可。

复杂度分析：

  • 时间复杂度：O(n)，其中n是字符串的长度，我们需要一个双层的遍历；

  • 空间复杂度：O(n)，其中n是字符串的长度，我们需要初始化一个二维数组。

    3. 代码实现

    1. /**
    2. * @param {string} s
    3. * @return {number}
    4. */
    5. var longestPalindromeSubseq = function(s) {
    6.   let len = s.length;
    8.   let dp = new Array(len)
    9.   for (let i = 0; i < len; i++) {
    10.       dp[i] = new Array(len).fill(0);
    11.   }
    13.   for (let i = len - 1; i >= 0; i--) {
    14.       dp[i][i] = 1;
    15.       for (let j = i+1; j < len; j++) {
    16.           if (s[i] === s[j]) {
    17.               dp[i][j] = dp[i+1][j-1] + 2;
    18.           } else {
    19.               dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1])
    20.           }
    21.       }
    22.   }
    23.   return dp[0][len-1];
    24. };

    4. 提交结果

    image.png