這道題是給你一個字符串校仑，記錄里面所有的回文字符串的個數(shù)。例如'abc' output = 3.分別為‘a(chǎn)’，‘b’概而，‘c’，而'aaa'. output = 6 分別為'a', 'a' , 'a', 'aa', 'aa', 'aaa'
思路：我當(dāng)時想到用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
