516. Longest Palindromic Subsequ

找到字符串s的最长回文序列的长度。

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

动态规划实现：
dp[i][j]表示 字符串s的下标范围[i, j]内的最长回文子序列的长度。不说文字，直接放代码

• 时间复杂度O(n^ 2), 空间复杂度O(n^2)
• Runtime: 256 ms, faster than 79.92%
• Memory Usage: 87.5 MB, less than 40.96%

/**
 * @param {string} s
 * @return {number}
 */
var longestPalindromeSubseq = function(s) {
  const len = s.length;
  const dp = new Array(len).fill().map(i => Array(len).fill(0));
  for (let i = len - 1; i >= 0; i--) {
    dp[i][i] = 1;
    for (let j = i + 1; j < len; 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][len - 1];
};