? ? ? ? 今天是動態規劃的最后一篇內容了，本篇主要是針對回文字符串這種“與眾不同”的遞推規律來進行講解

647. 回文子串

????????統計并返回這個字符串中?回文子串?的數目

暴力解法

????????兩層for循環，遍歷區間起始位置和終止位置，然后還需要一層遍歷判斷這個區間是不是回文。所以時間復雜度：O(n^3)

動態規劃

• 確定dp數組（dp table）以及下標的含義

????????如果大家做了很多這種子序列相關的題目，在定義dp數組的時候 很自然就會想題目求什么，我們就如何定義dp數組。

????????絕大多數題目確實是這樣，不過本題如果我們定義，dp[i] 為 下標i結尾的字符串有 dp[i]個回文串的話，我們會發現很難找到遞歸關系。dp[i] 和 dp[i-1] ，dp[i + 1] 看上去都沒啥關系。所以我們要看回文串的性質。

????????我們在判斷字符串S是否是回文，那么如果我們知道 s[1]，s[2]，s[3] 這個子串是回文的，那么只需要比較 s[0]和s[4]這兩個元素是否相同，如果相同的話，這個字符串s 就是回文串。那么此時我們是不是能找到一種遞歸關系，也就是判斷一個子字符串（字符串下標范圍[i,j]）是否回文，依賴于，子字符串（下標范圍[i + 1, j - 1]）） 是否是回文。

????????所以為了明確這種遞歸關系，我們的dp數組是要定義成二維dp數組。dp[i][j]（布爾類型）：表示區間范圍[i,j] （注意是左閉右閉）的子串是否是回文子串，如果是dp[i][j]為true，否則為false。

• 確定遞推公式（這個地方要和遍歷順序一起理解，遞推公式對于解題非常重要）

????????在確定遞推公式時，就要分析如下幾種情況。整體上是兩種，就是s[i]與s[j]相等，s[i]與s[j]不相等這兩種。

????????當s[i]與s[j]不相等，那沒啥好說的了，dp[i][j]一定是false。

????????當s[i]與s[j]相等時，這就復雜一些了，有如下三種情況

1. 情況一：下標i 與 j相同，同一個字符例如a，當然是回文子串
2. 情況二：下標i 與 j相差為1，例如aa，也是回文子串
3. 情況三：下標：i 與 j相差大于1的時候，例如cabac，此時s[i]與s[j]已經相同了，我們看i到j區間是不是回文子串就看aba是不是回文就可以了，那么aba的區間就是 i+1 與 j-1區間，這個區間是不是回文就看dp[i + 1][j - 1]是否為true。

• dp數組如何初始化??

????????dp[i][j]初始化為false。

• 確定遍歷順序

????????遍歷順序可就有點講究了。

????????首先從遞推公式中可以看出，情況三是根據dp[i + 1][j - 1]是否為true，在對dp[i][j]進行賦值true的。dp[i + 1][j - 1] 在 dp[i][j]的左下角所以一定要從下到上，從左到右遍歷，這樣保證dp[i + 1][j - 1]都是經過計算的。

????????總而言之，一個道理，都是為了保證dp[i + 1][j - 1]都是經過計算的。

• 舉例推導dp數組

????????舉例，輸入："aaa"，dp[i][j]狀態如下：

class Solution:def countSubstrings(self, s: str) -> int:dp = [[False] * len(s) for _ in range(len(s))]result = 0for i in range(len(s)-1, -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

雙指針法

回文子串的對稱中心有兩種情況：

• 奇數長度的回文子串（如 "aba"）：中心是單個字符（示例中的 "b"）。
• 偶數長度的回文子串（如 "abba"）：中心是兩個相鄰字符（示例中的 "bb"）。

中心擴展法的邏輯是：

• 枚舉字符串中每個可能的中心（單個字符或相鄰兩個字符）。
• 從中心向兩側擴展，判斷擴展后的子串是否為回文。
• 每擴展成功一次，就計數一個回文子串。

class Solution:def countSubstrings(self, s: str) -> int:result = 0for i in range(len(s)):result += self.extend(s, i, i, len(s)) #以i為中心result += self.extend(s, i, i+1, len(s)) #以i和i+1為中心return resultdef extend(self, s, i, j, n):res = 0while i >= 0 and j < n and s[i] == s[j]:i -= 1j += 1res += 1return res

516.最長回文子序列

????????這種回文子序列可以刪除元素是很難想的，因為規律不是很直觀。本題和上題的區別在于：回文子串是要連續的，回文子序列可不是連續的！?

• 確定dp數組（dp table）以及下標的含義

????????dp[i][j]：字符串s在[i, j]范圍內最長的回文子序列的長度為dp[i][j]。

• 確定遞推公式

????????在判斷回文子串的題目中，關鍵邏輯就是看s[i]與s[j]是否相同。

????????如果s[i]與s[j]相同，那么dp[i][j] = dp[i + 1][j - 1] + 2;

????????如果s[i]與s[j]不相同，說明s[i]和s[j]的同時加入 并不能增加[i,j]區間回文子序列的長度，那么分別加入s[i]、s[j]看看哪一個可以組成最長的回文子序列。那么dp[i][j]一定是取最大的，即：dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);

• dp數組如何初始化

????????當i與j相同，那么dp[i][j]一定是等于1的，即：一個字符的回文子序列長度就是1。其他情況dp[i][j]初始為0就行

• 確定遍歷順序

????????從遞歸公式中，可以看出，dp[i][j] 依賴于 dp[i + 1][j - 1] ，dp[i + 1][j] 和 dp[i][j - 1]，所以遍歷i的時候一定要從下到上遍歷，這樣才能保證下一行的數據是經過計算的。

• 遍歷模擬

class Solution:def longestPalindromeSubseq(self, s: str) -> int:dp = [[0] * len(s) for _ in range(len(s))]for i in range(len(s)):dp[i][i] = 1for i in range(len(s)-1, -1, -1):for j in range(i+1, len(s)):if s[i] == s[j]:dp[i][j] = dp[i+1][j-1] + 2else:dp[i][j] = max(dp[i+1][j], dp[i][j-1])return dp[0][-1]

動態規劃總結篇

代碼隨想錄——動態規劃總結篇

• 動態規劃基礎（初步感受遞推的關系）

• 背包問題系列（遞推二維到一維的理解）

• 打家劫舍系列（線性遞推順序的延伸）

• 股票系列（dp數組和數據輸出的巧妙設置）*

• 子序列系列（理解模擬遍歷的重要性）