516. 最长回文子序列(Medium)

题目描述

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

样例

Input: "bbbab"
Output: 4
# 最长的回文子序列, 解释: bbbb 

Input: "cbbd"
Output: 2
# 最长的回文子序列, 解释: bb 

题解

方法一：递归

在 5. 最长回文子串 的基础上进行改进，只是在判断回文子串的时候，进行修改。

• 如果 s 的第 i 个字符和第 j 个字符相同的话，向外扩展

  dp[i][j] = dp[i + 1][j - 1]

• 如果 s 的第 i 个字符和第 j 个字符不相同的话，跳过左 或者 右的节点

  dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])

注意点：

• dp[i][i] = 1 记录了长度为 1

方法二：动态规划

• 如果 s 的第 i 个字符和第 j 个字符相同的话，向外扩展

  dp[i][j] = dp[i + 1][j - 1] + 2

• 如果 s 的第 i 个字符和第 j 个字符不相同的话，跳过左 或者 右的节点

  expendAroundCenter(s, start, end + 1, deleteLetter + 1) // 跳过 end 点
  expendAroundCenter(s, start - 1, end, deleteLetter + 1) // 跳过 start 点

Go 示例

递归

// 超时 61/83
var ans int 

func longestPalindromeSubseq(s string) int {
    if len(s) < 2 {
        return len(s)
    }
    
    ans = 1

    for i:= 0; i < len(s); i++ {
        expendAroundCenter(s, i - 1, i + 1, 0)
        expendAroundCenter(s, i, i + 1, 0)
    }
    return ans 
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b 
}

func expendAroundCenter(s string, start int, end int , deleteLetter int ) {
    if start < 0 || end >= len(s) {
        return 
    }
    
    if s[start] == s[end] {
        ans = max(ans, end - start + 1 - deleteLetter)
        expendAroundCenter(s, start - 1, end + 1, deleteLetter)
    } else {
        expendAroundCenter(s, start, end + 1, deleteLetter + 1)
        expendAroundCenter(s, start - 1, end, deleteLetter + 1)
    }
}

动态规划

// AC
func max(a,b int) int {
    if a > b {
        return a 
    }
    return b 
}

func longestPalindromeSubseq(s string) int {
    n := len(s)
    if n < 2 {
        return n
    }

    dp := make([][]int, n)
    for i:= 0; i < n; i++ {
        dp[i] = make([]int, n)
    }

    for i:= n - 1; i >= 0; i-- { // 必须保证 i 计算的时候, i + 1 已经计算好了 ==> 从右向左
        dp[i][i] = 1 // 只有一个字符长度为 1
        for j:= i + 1; j < n; j++ { // 必须保证 j 计算的时候，j - 1 已经计算好了 ==> 从左向右
            if s[i] == s[j] {
                dp[i][j] = dp[i + 1][j - 1] + 2
            } else {
                dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
            }
        }
    }
    
    return dp[0][n - 1]
}