代码随想录day57|647. 回文子串516. 最长回文子序列

647. 回文子串

class Solution:
    def countSubstrings(self, s: str) -> int:
        #dp[i][j]表示从i 到j 的回文子串个数
        dp = [[False] * len(s) for _ in range(len(s))]
        result=0
        for i in range(len(s)-1,-1,-1):
            for j in range(i,len(s)):
                if s[i] == s[j]:
                    if j -i <=1:
                        dp[i][j]=True
                        result+=1
                    else:
                        dp[i][j] = dp[i+1][j-1]
                        if dp[i][j] == True:
                            result+=1
        return result

516. 最长回文子序列

class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        #dp[i][j]表示从i 到j 的回文子串个数
        dp = [[1] * len(s) for _ in range(len(s))]
        for i in range(len(s)-1,-1,-1):
            for j in range(i,len(s)):
                if s[i] == s[j]:
                    if j -i <=1:
                        dp[i][j]=j-i+1                 
                    else:
                        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]