介绍

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

下面是一个处理了所有情况的递归解决方案：

// Every single character is a palindrome of length 1
L(i, i) = 1 for all indexes i in given sequence

// IF first and last characters are not same
If (X[i] != X[j])  L(i, j) =  max{L(i + 1, j),L(i, j - 1)} 

// If there are only 2 characters and both are same
Else if (j == i + 1) L(i, j) = 2  

// If there are more than two characters, and first and last 
// characters are same
Else L(i, j) =  L(i + 1, j - 1) + 2 

重叠子问题：下面是 LPS 问题的一个简单的递归实现。该实现简单地遵循了上述的递归结构。

// A utility function to get max of two integers 
function max(x, y) {
  return (x > y) ? x : y;
}
 
// Returns the length of the longest palindromic subsequence in seq    
function lps(seq, i, j)
{
  // Base Case 1: If there is only 1 character
  if (i == j) return 1;
  // Base Case 2: If there are only 2 characters and both are same 
  if (seq[i] == seq[j] && i + 1 == j) return 2;
  // If the first and last characters match 
  if (seq[i] == seq[j]) return lps(seq, i + 1, j - 1) + 2;
  // If the first and last characters do not match 
  return max(lps(seq, i, j - 1), lps(seq, i + 1, j));
}

实现

JavaScript

// A utility function to get max of two integers
function max(x,y) {
  return (x > y)? x : y;
}
 
// Returns the length of the longest palindromic subsequence in seq
function lps(seq)
{
  let n = seq.length;
  let i, j, cl;
  // Create a table to store results of subproblems
  let L = new Array(n);
  for(let x=0;x<n;x++) {
      L[x] = new Array(n);
      for(let y = 0; y < n; y++) L[x][y] = 0;
  }
    
  // Strings of length 1 are palindrome of length 1
  for (i = 0; i < n; i++) L[i][i] = 1;
            
  // Build the table. Note that the lower diagonal values of table are useless and not filled in the process.
  // The values are filled in a manner similar to Matrix Chain Multiplication DP solution (See https://www.geeksforgeeks.org/matrix-chain-multiplication-dp-8/).
  // cl is length of substring
  for (cl = 2; cl <= n; cl++) {
    for (i = 0; i < n -cl + 1; i++) {
        j = i + cl - 1;
        if (seq[i] == seq[j] && cl == 2) L[i][j] = 2;
        else if (seq[i] == seq[j]) L[i][j] = L[i + 1][j - 1] + 2;
        else L[i][j] = max(L[i][j - 1], L[i + 1][j]);
    }
  }
            
  return L[0][n - 1];
}

或者：

/*
  LeetCode -> https://leetcode.com/problems/longest-palindromic-subsequence/

  Given a string s, find the longest palindromic subsequence's length in s.
  You may assume that the maximum length of s is 1000.

*/

const longestPalindromeSubsequence = function (s) {
  const n = s.length

  const dp = new Array(n).fill(0).map(item => new Array(n).fill(0).map(item => 0))

  // fill predefined for single character
  for (let i = 0; i < n; i++) dp[i][i] = 1;

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

  return dp[0][n - 1]
}

时间复杂度：O (n^2)，比 Naive Recursive 实现的最坏情况下的时间复杂度好得多。

辅助空间：O (n^2), 创建一个表

使用动态规划的缓存技术：想法是反转给定的输入字符串并检查最长的公共子序列的长度。这将是最长的公共子序列的答案。

// A Dynamic Programming based JavaScript program for LPS problem
// Returns the length of the longest palindromic subsequence in seq
let dp;
 
// Returns the length of the longest palindromic subsequence in seq
function lps(s1, s2, n1, n2) {
  if (n1 == 0 || n2 == 0) return 0;
  if (dp[n1][n2] != -1) return dp[n1][n2];
  if (s1[n1 - 1] == s2[n2 - 1]) return dp[n1][n2] = 1 + lps(s1, s2, n1 - 1, n2 - 1);
  return dp[n1][n2] = Math.max(lps(s1, s2, n1 - 1, n2), lps(s1, s2, n1, n2 - 1));
}

// * Driver program to test above functions */
 
let seq = "GEEKSFORGEEKS";
let n = seq.length;
dp = new Array(1001);
for(let i=0;i<1001;i++) dp[i] = new Array(1001).fill(-1);
let s2 = seq.split('').reverse().join('');
lps(s2, seq, n, n)

参考

• Longest Palindromic Subsequence | DP-12 - GeeksforGeeks (opens new window)