给定一个字符串s，找到其中最长的回文子序列长度。可以假设s的最大长度为1000。
输入:"bbbab"
输出:4
一个可能的最长回文子序列为 "bbbb"。
输入:"cbbd"
输出:2
一个可能的最长回文子序列为 "bb"。
分析：
令 DP[i][j]表示从第i到底j位（包含）的子串中，得到的最长回文子序列的长度，则DP[0][s.length-1]为所求。
找关系式：
s[i] === s[j]时， DP[i][j] = DP[i+1][j-1]
s[i] !== s[j]时， DP[i][j] = Math.max(DP[i+1][j], DP[i][j-1])
初始值： i===j时，DP[i][j] = 1;
/**
* @param {string} s
* @return {number}
*/
var longestPalindromeSubseq = function(s) {
const len = s.length;
let DP= new Array(len);
for(let i=0;i < len;i++) {
DP[i] = [];
DP[i][i] = 1;
}
for(let i = len -2; i>=0; i--) {
for(let j=i+1;j<len;j++) {
if(s[i] === s[j]) {
DP[i][j] = j-i===1 ? 2 : DP[i+1][j-1] + 2;
} else {
DP[i][j] = Math.max(DP[i+1][j], DP[i][j-1]) || 0;
}
}
}
return DP[0][len-1]
};
