最大回文串
正好让我回顾一下DP，动态规划比较经典的题目
Output: 3
Explanation: Three palindromic strings: "a", "b", "c".
Input: "aaa"
Output: 6
Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".
总之就是一个线性规划的问题，注意递归条件：
if (s[start] = s[end] and (dp[start+1][end-1] or end-start<3)):
dp[start][end] = 1
def countSubstrings(self, s):
"""
:type s: str
:rtype: int
"""
count = 0
l = len(s)
dp = [[0 for i in range(l)]for i in range(l)]
if len(s) == 0:
return count
for end in range(0,len(s)):
dp[end][end] = 1
count += 1
for start in range(0,end):
if s[start] == s[end] and (dp[start+1][end-1] or end-start<3):
dp[start][end] = 1
count += 1
return count
另附一开始的办法，直接reverse翻转字符串比较，对的就+1，注意str没有reverse，直接用切片操作：
def countSubstrings(self, s):
"""
:type s: str
:rtype: int
"""
count = 0
str1 = ''
str2 = ''
if len(s) == 0:
return count
for i in range(0,len(s)):
for j in range(i+1,len(s)+1):
str1 = s[i:j]
str2 = str1[::-1]
if str1 == str2:
count +=1
str1 = []
str2 = []
return count
