这道题是给你一个字符串，记录里面所有的回文字符串的个数。例如'abc' output = 3.分别为‘a’，‘b’，‘c’，而'aaa'. output = 6 分别为'a', 'a' , 'a', 'aa', 'aa', 'aaa'
思路：我当时想到用dp，但没有想到怎么遍历。可以i从头往后遍历，然后j从头遍历到i，这样中间都是之前计算过的。然后cnt每次遇到dp[i][j]为1就加1.
python代码：
class Solution:
def countSubstrings(self, s):
"""
:type s: str
:rtype: int
"""
n = len(s)
cnt = 0
dp = [[0] * n for i in range(n)]
for i in range(n):
for j in range(0, i+1):
if s[i] == s[j]:
if i == j:
dp[i][j] = 1
cnt += 1
elif abs(i-j) == 1:
dp[i][j] = 1
cnt += 1
elif abs(i - j) > 1:
dp[i][j] = dp[i-1][j+1]
if dp[i][j] == 1:
cnt += 1
return cnt
