0516. 最长回文子序列

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]
本站总访问量  次  |  您是本站第  位访问者