题解 | #编号子回文II#

• 题目考察的知识点 : 动态规划
• 题目解答方法的文字分析：

1. 定义一个二维数组 dp，其中 dp[i][j] 表示从编号 i 到编号 j 的子序列中最长的回文子序列的长度。对于每个子序列 s[i:j]，我们有两种情况：
2. 如果 s[i]=s[j]，那么它可能是回文子序列，取决于 s[i+1:j−1] 中最长的回文子序列的长度；
3. 如果 s[i]=s[j]，那么它不可能是回文子序列，需要在 s[i+1:j] 和 s[i:j−1] 中找到最长的回文子序列

• 本题解析所用的编程语言: Python
• 完整且正确的编程代码

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param s string字符串
# @return int整型
#
class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        n = len(s)
        if n == 0:
            return 0
        dp = [[0] * n for _ in range(n)]
        for i in range(n):
            dp[i][i] = 1
        for k in range(2, n + 1):
            for i in range(n - k + 1):
                j = i + k - 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][n - 1]