最大回文串
正好讓我回顧一下DP，動(dòng)態(tài)規(guī)劃比較經(jīng)典的題目

Output: 3
Explanation: Three palindromic strings: "a", "b", "c".
Input: "aaa"
Output: 6
Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".

總之就是一個(gè)線性規(guī)劃的問題，注意遞歸條件：

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翻轉(zhuǎn)字符串比較，對(duì)的就+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