找到字符串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];
};
