动态规划9：最长回文子序列

给定一个字符串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]
};