题目
给你一个字符串 s ，请你统计并返回这个字符串中回文子串的数目。回文字符串是正着读和倒过来读一样的字符串。子字符串是字符串中的由连续字符组成的一个序列。具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。
例：
输入：s = "abc"
输出：3
解释：三个回文子串: "a", "b", "c"
方法：动态规划
- dp[i][j] 表示下标为 [i, j] 组成的字符串是否为回文串，True 表示为回文串，False 表示不为回文串
- result 表示回文子串的数量
- 外部循环为从下到上的循环，内部循环为从左到右的循环
- 若首尾字符不同，那么一定不为回文串
- 若首尾字符相同，那么需要继续判断：若 i=j，即此时只有一个字符（e.g. a），那么一定为回文串；若 j-i=1，即只有两个字符且相等（e.g. aa），那么一定为回文串；若 j-i>1，即首尾字符间存在其他字符，那么此时应判断下标为 [i+1, j-1] 组成的字符串是否为回文串，即 dp[i+1][j-1]
class Solution(object):
def countSubstrings(self, s):
dp = [[False] * len(s) for row 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
elif dp[i+1][j-1]:
dp[i][j] = True
result += 1
return result
参考
代码相关：https://programmercarl.com/0647.%E5%9B%9E%E6%96%87%E5%AD%90%E4%B8%B2.html
