刷题第四十八天 647. 回文子串 516. 最长回文子序列

动态规划：

class Solution:
    def countSubstrings(self, s: str) -> int:
        #dp[i][j] s中i到j的子串是不是回文字串
        #if s[i] = s[j]:
        #   if j - i <= 1: dp[i][j] = True
        #   elif dp[i + 1][j - 1] = True: dp[i][j] = True
        result = 0
        dp = [[False] * 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] = True
                        result += 1
                    elif dp[i + 1][j - 1] == True:
                        dp[i][j] = True
                        result += 1
        return result

class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        # dp[i][j] s中i到j子串的最长回文子序列长度
        dp = [[0] * len(s) for _ in range(len(s))]
        for i in range(len(s)):
            dp[i][i] = 1
        for i in range(len(s) - 1, -1, -1):
            for j in range(i + 1, len(s)):
                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]

考虑s[i]!=s[j]的情况，就是判断能否加入s[i]（dp[i][j-1]）、s[j]（dp[i+1][j]）使得最长回文子序列更长。