0516. 最长回文子序列 #

标签：字符串、动态规划
难度：中等

题目大意 #

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

解题思路 #

动态规划求解。

定义状态 dp[i][j] 表示为：字符串 s 在 [i, j] 范围内的最长回文子序列长度。

则状态转移公式为：

如果 s[i] == s[j]，则 dp[i][j] 为 [i + 1, j - 1] 范围内最长回文子序列长度 + 2，即 dp[i][j] = dp[i + 1][j - 1] + 2。
如果 s[i] != s[j]，则 dp[i][j] 取决于以下两种情况，取其最大的一种：
- 加入 s[i] 所能组成的最长回文子序列长度，即：dp[i][j] = dp[i][j - 1]。
- 加入 s[j] 所能组成的最长回文子序列长度，即：dp[i][j] = dp[i - 1][j]。
下一步确定遍历方向。

由于 dp[i][j] 依赖于 dp[i + 1][j - 1]、dp[i + 1][j]、dp[i][j - 1]，所以我们应该按照从下到上、从左到右的顺序进行遍历。

最后输出 [0, size - 1] 范围内最长回文子序列长度，即 dp[0][size - 1] 为最终答案。

代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        size = len(s)
        dp = [[0 for _ in range(size)] for _ in range(size)]
        for i in range(size):
            dp[i][i] = 1

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