Leetcode 516. 最长回文子序列

class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        dp=[[0]*len(s) for i in range(len(s))]
        for j in range(len(s)):
            dp[j][j]=1
            for i in range(j-1,-1,-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][len(s)-1]

class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        dp=[1]*len(s)
        for j in range(len(s)):
            tmp=1
            for i in range(j-1,-1,-1):
                if s[i]==s[j]:
                    tmp,dp[i+1]=2 if j==i+1 else dp[i+1]+2,tmp
                else:
                    tmp,dp[i+1]=max(tmp,dp[i]),tmp
            dp[0]=tmp
        return dp[0]