You can look at this question before you do it 【leetcode】647. Palindrome string

subject

leetcode Original link

Give you a string s , Find the longest palindrome subsequence , And return the length of the sequence .
Subsequence is defined as ： Without changing the order of the remaining characters , A sequence formed by deleting some characters or not deleting any characters .

Example 1：
Input ：s = “bbbab”
Output ：4
explain ： The longest possible palindrome subsequence is “bbbb” .

Example 2：
Input ：s = “cbbd”
Output ：2
explain ： The longest possible palindrome subsequence is “bb” .

Tips ：
1 <= s.length <= 1000
s It's only made up of lowercase letters

Ideas

Dynamic programming

• set up dp[i][j] Indicates the interval [i,j] The length of the longest palindrome subsequence of is dp[i][j]
• Recurrence relation is divided into 2 In this case
  • When s[i] === s[j] when , It is divided into 3 In this case
    • j === i,dp[i][j] = 1
    • j - i === 1 , It's like 'aa' This situation ,dp[i][j] = 2
    • j - i > 1 , dp[i][j] = dp[i+1][j-1] + 2
  • When s[i] !== s[j] when , To delete one of the two characters , Take the one with a large palindrome string length after deletion , namely dp[i][j] = Math.max(dp[i+1][j] , dp[i][j-1])
• dp The array is initialized to 0 that will do
• Traversal order from left to right , From bottom to top

Code

/** * @param {string} s * @return {number} */
var longestPalindromeSubseq = function(s) {
    
    let len = s.length
    let ans = 0
    let dp = (new Array(len)).fill(false).map(x => (new Array(len)).fill(false))

    for(let i = len - 1 ; i >= 0 ; i--){
    
        for(let j = i ; j < len ; j++){
    
            if(s[i] === s[j]){
    
                if(j === i) dp[i][j] = 1
                else if(j - i === 1) dp[i][j] = 2
                else dp[i][j] = dp[i+1][j-1] + 2
            }else{
    
                dp[i][j] = Math.max(dp[i][j-1] , dp[i+1][j])
            }
            //  Update maximum length 
            ans = Math.max(ans , dp[i][j])
        }
    }

    return ans
};

Complexity

• Time complexity ：$O(n^2)$
• Spatial complexity ：$O(n^2)$

Pay attention to my special column , Update three times a day leetcode Answer key , Get stronger together ！