?

步驟一、確定狀態(tài):

確定dp數(shù)組及下標(biāo)含義
dp[i][j] 表示的是區(qū)間范圍[i,j] 的子串是否是回文子串

步驟二、推斷狀態(tài)方程:

在確定遞推公式時(shí)，就要分析如下幾種情況。 整體上是兩種，就是s[i]與s[j]相等，s[i]與s[j]不相等這兩種。 當(dāng)s[i]與s[j]不相等，那沒啥好說的了，dp[i][j]一定是false。 當(dāng)s[i]與s[j]相等時(shí)，這就復(fù)雜一些了，有如下三種情況 情況一:下標(biāo)i 與 j相同，同一個(gè)字符例如a，當(dāng)然是回文子串 情況二:下標(biāo)i 與 j相差為1，例如aa，也是文子串

情況三:下標(biāo):i 與 j相差大于1的時(shí)候，例如cabac，此時(shí)s[i]與s[j]已經(jīng)相同了，我們 看i到j(luò)區(qū)間是不是回文子串就看aba是不是回文就可以了，那么aba的區(qū)間就是 i+1 與 j-1區(qū)間，這個(gè)區(qū)間是不是回文就看dp[i + 1][j - 1]是否為true。

步驟三、規(guī)定初始條件:

初始條件:

全局初始化False， 而對(duì)角線初始化為True。

步驟四、計(jì)算順序:

遍歷i的時(shí)候一定要從下到 上遍歷，這樣才能保證，下 一行的數(shù)據(jù)是經(jīng)過計(jì)算的。 即逆向遍歷行，正向遍歷列。

class Solution:def countSubstrings(self, s: str) -> int:if len(s) == 1:return 1dp = [[False for _ in range(len(s))] for _ in range(len(s))]result = 0for i in range(len(s)):dp[i][i] = Truefor i in range(len(s), -1, -1):for j in range(i, len(s)):if s[i] == s[j]:if j - i <= 1:result += 1dp[i][j] = Trueelif dp[i+1][j-1]:result += 1dp[i][j] = Truereturn result

總結(jié)

以上是生活随笔為你收集整理的122. Leetcode 647. 回文子串 (动态规划-子序列问题)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。