思路

先寫個(gè)暴力 對(duì)所有的左右邊界進(jìn)行枚舉 時(shí)間復(fù)雜度O(n^3)

class Solution:
    def countSubstrings(self, s: str) -> int:
        # 計(jì)數(shù)問題 
        # 1.定義狀態(tài) dp[i][j]=k表示包含i到j(luò)元素的回文串的個(gè)數(shù) 左閉右閉
        # 2.轉(zhuǎn)移方程 如果固定i dp[i][j] = dp[i][j-1]+dp[j][j]

    
        # 先寫個(gè)暴力
        def judge(i,j):
            while(j>=i):
                if not s[i]==s[j]:
                    return False
                i+=1
                j-=1
            return True

        s_len = len(s)
        res = 0
        for i in range(s_len):
            for j in range(i,s_len):
                if judge(i,j):
                    res+=1
        return res

反思

超時(shí) 暴力很明顯的一點(diǎn)是重疊的子問題太多了，有些是回文串的我們已經(jīng)判斷過了，明顯具有重疊子問題

優(yōu)化

dp！ 三個(gè)步驟 定義狀態(tài) 轉(zhuǎn)移方程 基本情況
1.定義狀態(tài)：由暴力法我們發(fā)現(xiàn) 重疊的子問題是子串是否是回文串
那么我們定義狀態(tài)為 dp[i][j]表示 i,j段的串是否是回文串 是則是1 不是則為0
2.狀態(tài)轉(zhuǎn)移：對(duì)于一個(gè)dp[i][j] 如果str[i]!=str[j] 直接是false 如果相等則需討論:
如果 i==j:單個(gè)字符肯定是回文的
如果 i+1==j:說明由倆個(gè)相同字符組成也是回文的
除以上倆種：規(guī)約成子問題 dp[i+1][j-1]是不是回文的
3.遍歷方向：為什么需要考慮遍歷方向？ 因?yàn)槲覀兊臓顟B(tài)的轉(zhuǎn)移不是常規(guī)的[i-1][j-1] 而是 [i+1][j-1]
dp表如下
i,j-1 i,j
i+1,j-1 i+1,j+1
可以發(fā)現(xiàn)是從坐下推右上，并且我們假定右邊界大于等于左邊界 實(shí)際上只有dp表的上三角區(qū)域是有效的
4.基本情況：由2知i==j時(shí)都是true 即對(duì)角線上的都是True
至此 dp解法成立

實(shí)現(xiàn)

class Solution:
    def countSubstrings(self, s: str) -> int:
        # 計(jì)數(shù)問題 
        # 1.定義狀態(tài) dp[i][j]=1 or 0 表示包含i到j(luò)元素的左閉右閉串是否為回文串 是1 否0
        # 2.轉(zhuǎn)移方程 如果固定i dp[i][j] = dp[i][j-1]+dp[j][j] 
        # 狀態(tài)轉(zhuǎn)移：對(duì)于一個(gè)dp[i][j] 如果str[i]!=str[j] 直接是false 如果相等則需討論:
        # 如果 i==j:單個(gè)字符肯定是回文的
        # 如果 i+1==j:說明由倆個(gè)相同字符組成也是回文的
        # 除以上倆種：規(guī)約成子問題 dp[i+1][j-1]是不是回文的
        s_len = len(s)
        ans =0
        dp = [[0]*s_len for _ in range(s_len)]
        
        # # 基本情況
        # for i in range(s_len):
        #     dp[i][i]=1
        # print(dp)
        # 狀態(tài)轉(zhuǎn)移
        for i in range(s_len-1,-1,-1): # i 從大往小
            # print(i)
            for j in range(i,s_len): # j 從小往大
                if s[i]==s[j]:
                    if j-i<=1: # 處理單個(gè)和倆個(gè)的情況
                        dp[i][j] = 1
                        ans+=1
                    else:
                        dp[i][j]=dp[i+1][j-1]
                        if dp[i][j]==1:
                            ans+=1
                else:
                    dp[i][j]=0
        return ans