[516][中等][动态规划] 最长回文子序列

题目描述

516. 最长回文子序列

给定一个字符串 s ，找到其中最长的回文子序列，并返回该序列的长度。可以假设 s 的最大长度为 1000 。

示例 1:

输入:
"bbbab"
输出:
4

一个可能的最长回文子序列为 "bbbb"。

示例 2:

输入:
"cbbd"
输出:
2

一个可能的最长回文子序列为 "bb"。

提示：

• 1 <= s.length <= 1000

• s 只包含小写英文字母

解题思路

使用动态规划的方法.

状态

f[i][j] 表示 s 的第 i 个字符到第 j 个字符组成的子串中，最长的回文序列长度是多少。

转移方程

如果 s 的第 i 个字符和第 j 个字符相同的话

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

如果 s 的第 i 个字符和第 j 个字符不同的话

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

初始化

f[i][i] = 1 单个字符的最长回文序列是 1

结果

f[0][n - 1]

遍历顺序

由于计算f[i][j]时可能需要 f[i+1][j-1] 即左下, f[i+1][j] 即下方, f[i][j - 1]即左方,

对角线的值在初始化时都确定时1, 因此在遍历时, i从最后向前遍历, j从i + 1遍历到n - 1, 这样可以保证每个子问题都已经算好了.

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

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

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

参考资料

• 动态规划，四要素