代码随想录 -- 动态规划 -- 最长回文子序列

516. 最长回文子序列 - 力扣（LeetCode）

思路：

dp数组的含义：

• dp[i][j]：字符串s从i到j的最长回文子序列的长度为dp[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][j-1],dp[i+1][j])

初始化：

• 当i=j时：dp[i][j]=1

遍历顺序：

• 从下到上，从左到右

最终返回dp[0][n-1]

class Solution(object):
    def longestPalindromeSubseq(self, s):
        n=len(s)
        dp=[[0]*n for _ in range(n)]
        for i in range(n):
            dp[i][i]=1
        for i in range(n-1,-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][j-1],dp[i+1][j])
        # print dp
        return dp[0][n-1]