题解 | 最长回文子序列

动态规划递推核心思想

状态定义: dp[i][j]表示字符串s从索引i到j的最长回文子序列长度。

状态转移方程: 如果s[i] == s[j]，则dp[i][j] = dp[i+1][j-1] + 2。 如果s[i] != s[j]，则dp[i][j] = max(dp[i+1][j], dp[i][j-1])。

边界条件: 当i == j时，dp[i][i] = 1，因为单个字符本身是回文。

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param s string字符串 一个字符串由小写字母构成，长度小于5000
# @return int整型
#
class Solution:
    def longestPalindromeSubSeq(self , s: str) -> int:
        # write code here
        n = len(s)
        dp = [[0]*n for _ in range(n)]#递推公式表示为下标i到j最长的回文序列长度
        for i in range(n-1,-1,-1):#左边界下标不断左移
            dp[i][i] = 1#单个字符的回文子序列长度为1
            for j in range(i+1,n):#右边界下标从当前左下标开始不断右移
                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]#表示匆匆下标0到下标n的最长回文子串长度

力扣大神的多种方法解答，可以参考。

***教你一步步思考动态规划：从记忆化搜索到递推到空间优化！（Python/Java/C++/Go）