如何优化最长回文子序列DP代码？解决测试用例与复杂度问题

原代码的核心问题 #

你的代码目前存在两个关键问题：

1. 功能不符合需求：当前函数返回的是最长回文子序列的长度，而非子序列本身。
2. 空间复杂度较高：使用了O(n²)的二维DP数组，存在优化空间。

修复与优化方案 #

方案1：二维DP+回溯构造子序列 #

先修正功能，通过回溯DP表来构造实际的最长回文子序列，再逐步优化空间。

function longestPalindromicSubsequence(str) {
  const n = str.length;
  if (n === 0) return "";
  
  // 创建DP表，dp[i][j]表示str[i..j]区间内最长回文子序列的长度
  const dp = Array.from({ length: n }, () => Array(n).fill(0));
  
  // 初始化长度为1的子序列（单个字符本身就是回文）
  for (let i = 0; i < n; i++) {
    dp[i][i] = 1;
  }
  
  // 按子序列长度从2到n填充DP表
  for (let cl = 2; cl <= n; cl++) {
    for (let i = 0; i <= n - cl; i++) {
      const j = i + cl - 1;
      if (str[i] === str[j]) {
        // 两端字符相等，长度为内部子序列长度+2（长度为2时直接是2）
        dp[i][j] = cl === 2 ? 2 : dp[i + 1][j - 1] + 2;
      } else {
        // 两端字符不等，取左右子序列的最大值
        dp[i][j] = Math.max(dp[i][j - 1], dp[i + 1][j]);
      }
    }
  }
  
  // 回溯DP表，构造最长回文子序列
  let i = 0, j = n - 1;
  const result = [];
  
  while (i <= j) {
    if (str[i] === str[j]) {
      // 两端字符相等，加入结果，向中间收缩
      result.push(str[i]);
      i++;
      j--;
    } else if (dp[i][j - 1] > dp[i + 1][j]) {
      // 左侧子序列更长，向左移动右指针
      j--;
    } else {
      // 右侧子序列更长，向右移动左指针
      i++;
    }
  }
  
  // 拼接结果：前半部分 + 反转的后半部分（奇数长度时去掉中间重复的字符）
  const isOddLen = dp[0][n - 1] % 2 === 1;
  const firstHalf = result.join('');
  const secondHalf = isOddLen ? result.slice(0, -1).reverse().join('') : result.reverse().join('');
  
  return firstHalf + secondHalf;
}

方案2：空间优化为O(n)的一维DP #

观察二维DP表的填充逻辑，计算长度为cl的子序列时，只需要用到长度为cl-1和cl-2的结果，因此可以用一维数组替代二维数组，将空间复杂度从O(n²)降至O(n)。

function longestPalindromicSubsequence(str) {
  const n = str.length;
  if (n === 0) return "";
  
  // 一维DP数组，dp[j]表示当前处理区间内str[i..j]的最长回文子序列长度
  let dp = Array(n).fill(0);
  
  // 从后往前遍历左指针i
  for (let i = n - 1; i >= 0; i--) {
    let prev = 0; // 保存dp[i+1][j-1]的旧值，避免被覆盖
    dp[i] = 1; // 单个字符的回文长度为1
    
    for (let j = i + 1; j < n; j++) {
      const temp = dp[j]; // 先保存当前dp[j]的值，后续作为prev使用
      if (str[i] === str[j]) {
        dp[j] = prev + 2;
      } else {
        dp[j] = Math.max(dp[j], dp[j - 1]);
      }
      prev = temp;
    }
  }
  
  // 根据一维DP结果回溯构造子序列
  let i = 0, j = n - 1;
  const result = [];
  const maxLen = dp[n - 1];
  let currentLen = maxLen;
  
  while (currentLen > 0) {
    if (i === j) {
      // 处理奇数长度的中间字符
      result.push(str[i]);
      break;
    }
    if (str[i] === str[j]) {
      result.push(str[i]);
      i++;
      j--;
      currentLen -= 2;
    } else if (dp[j - 1] === currentLen) {
      j--;
    } else {
      i++;
    }
  }
  
  // 拼接最终结果
  const isOddLen = maxLen % 2 === 1;
  const firstHalf = result.join('');
  const secondHalf = isOddLen ? result.slice(0, -1).reverse().join('') : result.reverse().join('');
  
  return firstHalf + secondHalf;
}

测试示例 #

• 输入 "bbbab"，返回 "bbbb"（或其他等价的最长回文子序列）
• 输入 "cbbd"，返回 "bb"

内容的提问来源于stack exchange，提问作者user21196765