516. 最长回文子序列

题目

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

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

示例 1：

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

示例 2：

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

提示：

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

解答

思路

对于区间 DP 问题，我们会把问题规模缩小的 数组的中间区间 上，而不仅仅是线性 DP 的前缀或后缀。

最简单的思路：求 s 和 s[::-1] 的 LCS 即可，这是由于回文子序列的回文特性。

代码

class Solution:
    def longestCommonSubsequence(self, s: str, t: str) -> int:
        n = len(s)
        m = len(t)

        f = [0] * (m + 1)

        for x in s:
            pre = f[0]
            for j, y in enumerate(t):
                tmp = f[j + 1] # 上一轮的 f[i][j]

                if x == y:
                    f[j + 1] = pre + 1
                else:
                    f[j + 1] = max(f[j + 1], f[j])
                
                pre = tmp

        return f[m]
    
    def longestPalindromeSubseq(self, s: str) -> int:
        return self.longestCommonSubsequence(s, s[::-1])

思路：选或不选

子序列本质上就是 原序列中的数经过选或不选 的抉择后得到的新序列。这里我们采用从两侧向内缩小问题规模：

• 当前操作：
  • 若 s[i] == s[j]，二者都选，从 dfs(i + 1, j - 1) + 2 转移过来
  • 若 s[i] != s[j] 且不选 s[i]，从 dfs(i + 1, j) 转移过来
  • 若 s[i] != s[j] 且不选 s[j]，从 dfs(i, j - 1) 转移过来
  • 二者取最大值
• 当前问题：从 s[i] 到 s[j] 的最长回文子序列的长度 dfs(i, j)
• 它的子问题：见当前操作

回溯方程：

$$\text{dfs}(i,j)=\{\begin{array}{lll}\text{dfs}(i+1,j-1)+2& & s[i]=s[j]\\ max(\text{dfs}(i+1,j),\text{dfs}(i,j-1))& & s[i]\ne s[j]\end{array}$$

递归边界：

• dfs(i, i) = 1
• dfs(i + 1, i) = 0，此时区间长度为 -1，自然是没有子序列的
• 例如 bb 会从 dfs(i, i + 1) 转移到 dfs(i + 1, i)

递归入口：dfs(0, n - 1)

由于是二维的，因此状态有 $O(n^2)$ 个，每个状态需要 $O(1)$ 时间计算：

• 时间复杂度为 $O(n^2)$
• 空间复杂度为 $O(n^2)$

代码

class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        n = len(s)

        @cache
        def dfs(i, j):
            if i > j:
                return 0
            
            if i == j:
                return 1
            
            if s[i] == s[j]:
                return dfs(i + 1, j - 1) + 2
            
            return max(dfs(i + 1, j), dfs(i, j - 1))
        
        return dfs(0, n - 1)

思路：递推

$$f[i][j]=\{\begin{array}{ll}0& i>j\\ 1& i=j\\ f[i+1][j-1]+2& s[i]=s[j]\\ max(f[i+1][j],f[i][j-1])& s[i]\ne s[j]\end{array}$$

注意循环顺序！

• 由于 f[i][j] 是从 f[i + 1][] 转移过来，因此 i 需要倒序枚举
• 由于 f[i][j] 是从 f[i][j - 1] 转移过来，因此 j 需要正序枚举

形象表述为：

• 当 s[i] == s[j] 时，f[i][j] 从它的 左下角 转移过来，因此 i 需要倒序枚举
• 当 s[i] != s[j] 时，f[i][j] 从它的正下方和正左方转移过来，因此 j 需要正序枚举

递推答案为 f[0][n - 1]。

代码

class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        n = len(s)

        f = [[0] * n for _ in range(n)]

        for i in range(n - 1, -1, -1):
            f[i][i] = 1

            for j in range(i + 1, n):
                if s[i] == s[j]:
                    f[i][j] = f[i + 1][j - 1] + 2
                else:
                    f[i][j] = max(f[i + 1][j], f[i][j - 1])
        
        return f[0][n - 1]

思路：空间优化

从左往右枚举 j 说明 f[i + 1][j - 1] 会被后面计算的 f[i][j - 1] 给覆盖掉。

代码

class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        n = len(s)

        f = [0] * n

        for i in range(n - 1, -1, -1):
            f[i] = 1
            pre = 0 # f[i + 1][j - 1]，存储 f[j - 1]

            for j in range(i + 1, n):
                tmp = f[j]

                if s[i] == s[j]:
                    f[j] = pre + 2
                else:
                    f[j] = max(f[j], f[j - 1])
                
                pre = tmp
            
        return f[-1]