最长回文子序列

给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。
子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
var longestPalindromeSubseq = function(s) {
    let dp = new Array(s.length).fill().map(val =>Array(s.length).fill(0))
    // for(let i = 0;i<s.length;i++){
    //     dp[i][i] = 1
    // }
    for(let i = s.length-1;i>=0;i--){
        for(j = i;j<s.length;j++){
            if(s[i]==s[j]){
                if(j-i<1){
                    dp[i][j] = 1
                }
                else{
                    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][s.length-1]
};