516.最长回文子序列

链接：516.最长回文子序列
难度：Medium
标签：字符串、动态规划
简介：给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。

题解 1 - typescript

• 编辑时间：2021-08-12
• 执行用时：212ms
• 内存消耗：86MB
• 编程语言：typescript
• 解法介绍：动态规划,dp[i][j]=以 i 结尾 j 开头的子序列的最大值。

function longestPalindromeSubseq(s: string): number {
  const n = s.length;
  if (n === 1) return 1;
  const dp = new Array(n).fill(0).map(_ => new Array(n).fill(0));
  for (let i = n - 2; i >= 0; i--) {
    dp[i][i] = 1;
    const cl = s[i];
    for (let j = i + 1; j < n; j++) {
      const cr = s[j];
      if (cl === cr) {
        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];
}