最长回文子序列js

给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。

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

示例 1：

输入：s = "bbbab"
输出：4
解释：一个可能的最长回文子序列为 "bbbb" 。
示例 2：

输入：s = "cbbd"
输出：2
解释：一个可能的最长回文子序列为 "bb" 。

提示：

1 <= s.length <= 1000
s 仅由小写英文字母组成

对于一个子序列而言，如果它是回文子序列，并且长度大于 2，那么将它首尾的两个字符去除之后，它仍然是个回文子序列。因此可以用动态规划的方法计算给定字符串的最长回文子序列。

动态规划五部曲：

1.确定dp数组的含义：dp[i][j]：字符串s在[i, j]范围内最⻓的回⽂⼦序列的⻓度为dp[i][j]。

2.确定动态规划转移方程：关键是判断s[i]和s[j]是否相同，如果s[i]和s[j]相同，意味着字符串s的区间【i,j】内的最长回文子序列的在s【i+1,j-1】的最长回文子序列的基础上+2，也就是：

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])；

举个例子：bbbab 假设i=3，j=4，【a,b】区间的最大回文子序列，首先判断a != b，那么我们可以想到，【a,b】区间的最大回文子序列长度要么就是a的长度，要么就是b的长度，因此dp[3][4]=Math.max(dp[4][4],dp[3][3]) = 1。

3.确定初始值：由于单个字符一定是回文子序列，因此可以得到dp[i][i] = 1 ;

4.确定遍历顺序：从递推公式dp[i][j] = dp[i + 1][j - 1] + 2 和 dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]) 可以看出，dp[i][j]是依 赖于dp[i + 1][j - 1] 和 dp[i + 1][j]， 也就是从矩阵的⻆度来说，dp[i][j]下⼀⾏的数据。 所以遍历i的时候⼀定要从下到上遍历，这样才能保证，下⼀⾏的数据是经过计算的。

5.举例推导dp数组：

	b	b	b	a	b
b	1	2	3	3	4
b		1	2	2	3
b			1	1	3
a				1	1
b					1

结果返回dp[0][n-1]就是最大回文子序列，表示s【0，n-1】区间内最大的回文子序列长度，也就是一整个字符串的最大回文子序列长度。

var longestPalindromeSubseq = function(s) {
    const n = s.length
    const dp = new Array(n).fill(0).map(()=>new Array(n).fill(0))
    for(let i = n-1 ; i >= 0; i--) {
        dp[i][i] = 1
        for(let j = i+1; j < n ; 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][n-1]
};