516. 最长回文子序列

Difficulty
Medium
Tags
动态规划
URL
https://leetcode-cn.com/problems/longest-palindromic-subsequence/
Star
给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。
子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。
示例 1：
输入：s = "bbbab"
输出：4
解释：一个可能的最长回文子序列为 "bbbb" 。
示例 2：
输入：s = "cbbd"
输出：2
解释：一个可能的最长回文子序列为 "bb" 。
提示：
  • 1 <= s.length <= 1000
  • s 仅由小写英文字母组成

法1 动态规划 双序列型

思路
题目虽然给了一个字符串，但其实也可以看作双序列类型的题目。
新建一个字符串t，为s字符串的逆序。这样判断s字符串中最长回文子序列的问题就转化为s和t中最长公共子序列问题了。具体思路参见
🕢
1143. 最长公共子序列
题解
class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        t = s[::-1]

        dp = [[0]*(len(t)+1) for _ in range(len(s)+1)]
        for i in range(1, len(dp)):
            for j in range(1, len(dp[0])):
                if s[i-1] == t[j-1]:
                    dp[i][j] = dp[i-1][j-1] + 1
                else:
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1])
            
        return dp[-1][-1]

法2 动态规划 区间型

思路
定义状态dp[i][j] 表示子数组s[i:j+1] 之间的最长回文子序列。那么dp[i][j]则：
  • 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])
整个动态规划的过程，即相当于在填充如下表格：
notion imagenotion image
需要注意如下特殊情况。当两个字符挨着且相等的时候，也是从左下角 + 2，只不过此时左下角默认为0，也就不用特殊考虑了
notion imagenotion image
初始化的时候，仅仅需要将对角线上的初始化为1。
然后判断的时候，并不需要专门取判断j = i+ 1 的特殊情况。因为j = i + 1 时，表明此时两个字符挨着，然后只有相等才会用到dp[i+1][j-1]， 而此时dp[i+1][j-1] 默认就是0，所以不需要专门考虑，见上图
题解
class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        if len(s) <= 1:
            return len(s)

        dp = [[0] * len(s) for _ in range(len(s))]

        for i in range(0, len(s)):
            dp[i][i] = 1

        for i in range(len(s)-1, -1, -1):
            for j in range(i+1, len(s), 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][-1]


# 可以将上述代码 优化，将初始化也融合到状态转移时刻进行初始化
class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        if len(s) <= 1:
            return len(s)

        dp = [[0] * len(s) for _ in range(len(s))]           

        for i in range(len(s)-1, -1, -1):
            # 初始化
            dp[i][i] = 1
            for j in range(i+1, len(s), 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][-1]