代碼隨想錄算法訓練營第60天｜動態規劃part17｜ 647. 回文子串、516.最長回文子序列、動態規劃總結篇

647. 回文子串

647. 回文子串

思路：

暴力解法

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

動態規劃

動規五部曲：

1. 確定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。

2. 確定遞推公式

在確定遞推公式時，就要分析如下幾種情況。

整體上是兩種，就是s[i]與s[j]相等，s[i]與s[j]不相等這兩種。

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

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

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

以上三種情況分析完了，那么遞歸公式如下：

if (s[i] == s[j]) {if (j - i <= 1) { // 情況一 和 情況二result++;dp[i][j] = true;} else if (dp[i + 1][j - 1]) { // 情況三result++;dp[i][j] = true;}
}

result就是統計回文子串的數量。

注意這里我沒有列出當s[i]與s[j]不相等的時候，因為在下面dp[i][j]初始化的時候，就初始為false。

3. dp數組如何初始化

dp[i][j]可以初始化為true么？ 當然不行，怎能剛開始就全都匹配上了。

所以dp[i][j]初始化為false。

4. 確定遍歷順序

首先從遞推公式中可以看出，情況三是根據dp[i + 1][j - 1]是否為true，在對dp[i][j]進行賦值true的。

dp[i + 1][j - 1] 在 dp[i][j]的左下角，如圖：

如果這矩陣是從上到下，從左到右遍歷，那么會用到沒有計算過的dp[i + 1][j - 1]，也就是根據不確定是不是回文的區間[i+1,j-1]，來判斷了[i,j]是不是回文，那結果一定是不對的。

所以一定要從下到上，從左到右遍歷，這樣保證dp[i + 1][j - 1]都是經過計算的。

有的代碼實現是優先遍歷列，然后遍歷行，其實也是一個道理，都是為了保證dp[i + 1][j - 1]都是經過計算的。

for (int i = s.size() - 1; i >= 0; i--) {  // 注意遍歷順序for (int j = i; j < s.size(); j++) {if (s[i] == s[j]) {if (j - i <= 1) { // 情況一 和 情況二result++;dp[i][j] = true;} else if (dp[i + 1][j - 1]) { // 情況三result++;dp[i][j] = true;}}}
}

5. 舉例推導dp數組

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

圖中有6個true，所以就是有6個回文子串。

注意因為dp[i][j]的定義，所以j一定是大于等于i的，那么在填充dp[i][j]的時候一定是只填充右上半部分。

代碼：

python

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

雙指針法

動態規劃的空間復雜度是偏高的，我們再看一下雙指針法。

首先確定回文串，就是找中心然后向兩邊擴散看是不是對稱的就可以了。

在遍歷中心點的時候，要注意中心點有兩種情況。

一個元素可以作為中心點，兩個元素也可以作為中心點。

那么有人同學問了，三個元素還可以做中心點呢。其實三個元素就可以由一個元素左右添加元素得到，四個元素則可以由兩個元素左右添加元素得到。

所以我們在計算的時候，要注意一個元素為中心點和兩個元素為中心點的情況。

這兩種情況可以放在一起計算，但分別計算思路更清晰，我傾向于分別計算，代碼如下：

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.最長回文子序列

516.最長回文子序列

思路：

動規五部曲分析如下：

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

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

2. 確定遞推公式

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

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

如圖：

（如果這里看不懂，回憶一下dp[i][j]的定義）

如果s[i]與s[j]不相同，說明s[i]和s[j]的同時加入 并不能增加[i,j]區間回文子序列的長度，那么分別加入s[i]、s[j]看看哪一個可以組成最長的回文子序列。

加入s[j]的回文子序列長度為dp[i + 1][j]。

加入s[i]的回文子序列長度為dp[i][j - 1]。

那么dp[i][j]一定是取最大的，即：dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);

代碼如下：

if (s[i] == s[j]) {dp[i][j] = dp[i + 1][j - 1] + 2;
} else {dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
}

3. dp數組如何初始化

首先要考慮當i 和j 相同的情況，從遞推公式：dp[i][j] = dp[i + 1][j - 1] + 2; 可以看出 遞推公式是計算不到 i 和j相同時候的情況。

所以需要手動初始化一下，當i與j相同，那么dp[i][j]一定是等于1的，即：一個字符的回文子序列長度就是1。

其他情況dp[i][j]初始為0就行，這樣遞推公式：dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]); 中dp[i][j]才不會被初始值覆蓋。

vector<vector<int>> dp(s.size(), vector<int>(s.size(), 0));
for (int i = 0; i < s.size(); i++) dp[i][i] = 1;

4. 確定遍歷順序

從遞歸公式中，可以看出，dp[i][j] 依賴于 dp[i + 1][j - 1] ，dp[i + 1][j] 和 dp[i][j - 1]，如圖：

所以遍歷i的時候一定要從下到上遍歷，這樣才能保證下一行的數據是經過計算的。

代碼如下：

for (int i = s.size() - 1; i >= 0; i--) {for (int j = i + 1; j < s.size(); j++) {if (s[i] == s[j]) {dp[i][j] = dp[i + 1][j - 1] + 2;} else {dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);}}
}

5. 舉例推導dp數組

代碼：

python

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]

動態規劃總結篇

動態規劃總結篇