647. Palindromic Substrings刷题笔记

用动态规划可以做，应该可以优化为只有两个表，而且不用每次res都加

class Solution:
    def countSubstrings(self, s: str) -> int:
        n = len(s)
        dp = [[0]*n for _ in range(n)]
        res = 0
        
        for i in range(n-1, -1, -1):
            for j in range(i,n):
                dp[i][j] = s[i]==s[j] and ((j-i)<2 or dp[i+1][j-1])
                res += dp[i][j]
        return res