---

前言

那么，什么是動態規劃中的回文子串問題呢？

動態規劃中的回文子串問題是一個經典的字符串處理問題。具體描述為：給定一個字符串，要求找出該字符串中所有的回文子串。回文子串是指從左到右和從右到左讀起來都一樣的字符串片段。
例如，對于字符串 “abcba”，其中的 “a”“b”“c”“aba”“bcb”“abcba” 都是回文子串。
解決這個問題通常使用動態規劃的方法。定義一個二維布爾數組dp[i][j]，表示字符串中從索引i到索引j的子串是否為回文子串。初始化時，單個字符一定是回文子串，即dp[i][i] = true。然后，從長度為 2 的子串開始逐步計算到整個字符串的長度。對于長度大于 1 的子串，如果兩端字符相等，即s[i] == s[j]，并且去掉兩端字符后的子串也是回文子串，即dp[i + 1][j - 1] = true，那么這個子串就是回文子串，dp[i][j] = true。通過這樣的動態規劃過程，可以高效地找出字符串中的所有回文子串，時間復雜度通常為O(n²)，其中n是字符串的長度。

下面本文將通過以例題的形式詳細闡述動態規劃中的回文子串問題。

例題

一、回文子串

1. 題目鏈接：回文子串
2. 題目描述：

給你?個字符串 s ，請你統計并返回這個字符串中 回文字串的數目。 回文字符串 是正著讀和倒過來讀?樣的字符串。 ?字符串 是字符串中的由連續字符組成的?個序列。 具有不同開始位置或結束位置的子串，即使是由相同的字符組成，也會被視作不同的子串。
示例 1：
輸入：s = “abc”
輸出：3
解釋：三個回文子串: “a”, “b”, “c”
示例 2：
輸入：s = “aaa”
輸出：6
解釋：6個回文子串: “a”, “a”, “a”, “aa”, “aa”, “aaa”
提示：1 <= s.length <= 1000
s 由小寫英文字母組成

3. 解法（動態規劃）： 算法思路： 我們可以先「預處理」?下，將所有子串「是否回文」的信息統計在 dp 表里面，然后直接在表里面統計 true 的個數即可。
   狀態表示：為了能表示出來所有的子串，我們可以創建?個 n * n 的?維 dp 表，只用到「上三角部分」 即可。 其中， dp[i][j] 表示： s 字符串 [i, j] 的子串，是否是回文串。
   狀態轉移方程： 對于回文串，我們一般分析一個「區間兩頭」的元素：
   i. 當 s[i] != s[j] 的時候：不可能是回?串， dp[i][j] = 0 ；
   ii. 當 s[i] == s[j] 的時候：根據?度分三種情況討論：
   ? 長度為 1 ，也就是 i == j ：此時?定是回文串， dp[i][j] = true ；
   ? 長度為 2 ，也就是 i + 1 == j ：此時也?定是回文串， dp[i][j] = true ；
   ? 長度大于 2 ，此時要去看看 [i + 1, j - 1] 區間的子串是否回文： dp[i][j] = dp[i + 1][j - 1] 。 綜上，狀態轉移方程分情況談論即可。
   初始化：因為我們的狀態轉移方程分析的很細致，因此無需初始化。
   填表順序： 根據「狀態轉移方程」，我們需要「從下往上」填寫每?行，每?行的順序無所謂。
   返回值： 根據「狀態表示和題母要求」，我們需要返回 dp 表中 true 的個數。

4. 代碼示例：

 public int countSubstrings(String s) {// 1. 創建 dp 表// 2. 初始化// 3. 填表// 4. 返回值int n = s.length();boolean[][] dp = new boolean[n][n];int ret = 0;for (int i = n - 1; i >= 0; i--) {for (int j = i; j < n; j++) {if (s.charAt(i) == s.charAt(j))dp[i][j] = i + 1 < j ? dp[i + 1][j - 1] : true;if (dp[i][j])ret++;}}return ret;}

二、 最長回文子串

1. 題目鏈接：最長回文子串
2. 題目描述：

給你?個字符串 s，找到 s 中最長的回文子串。 如果字符串的反序與原始字符串相同，則該字符串稱為回文字符串。
示例 1： 輸入：s = “babad” 輸出：“bab” 解釋：“aba” 同樣是符合題意的答案。
示例 2： 輸入：s = “cbbd” 輸出：“bb”
提示：1 <= s.length <= 1000
s 僅由數字和英文字母組成

3. 解法（動態規劃）：
   算法思路：
   a. 我們可以先? dp 表統計出「所有子串是否回文」的信息
   b. 然后根據 dp 表示 true 的位置，得到回文串的「起始位置」和「長度」。
   那么我們就可以在表中找出最長回文串

4. 代碼示例：

public String longestPalindrome(String s) {// 1. 創建 dp 表// 2. 初始化// 3. 填表// 4. 返回值int n = s.length();boolean[][] dp = new boolean[n][n];int begin = 0, len = 1; // 標記?下最??串的起始位置和?度for (int i = n - 1; i >= 0; i--) {for (int j = i; j < n; j++) {if (s.charAt(i) == s.charAt(j))dp[i][j] = i + 1 < j ? dp[i + 1][j - 1] : true;if (dp[i][j] && j - i + 1 > len) {len = j - i + 1;begin = i;}}}return s.substring(begin, begin + len);}

三、回文串分割IV

1. 題目鏈接：回文串分割IV
2. 題目描述：

給你?個字符串 s ，如果可以將它分割成三個非空回文子字符串，那么返回 true ，否則返 回 false 。 當?個字符串正著讀和反著讀是?模?樣的，就稱其為回文字符串 。
示例 1： 輸入：s = “abcbdd” 輸出：true
解釋：“abcbdd” = “a” + “bcb” + “dd”，三個?字符串都是回?的。
示例 2： 輸入：s = “bcbddxy” 輸出：false
解釋：s 沒辦法被分割成 3 個回文子字符串。
提?： 3 <= s.length <= 2000
s 只包含?寫英?字?。

3. 解法（動態規劃）：
   算法思路： 題目要求?個字符串被分成「三個非空回文子串」，乍?看，要表?的狀態很多，有些無從下手。 其實，我們可以把它拆成「兩個小問題」：
   i. 動態規劃求解字符串中的?段非空子串是否是回文串；
   ii. 枚舉三個子串除字符串端點外的起止點，查詢這三段非空子串是否是回文串。 那么這道困難題就免秒變為簡單題啦，變成了?道枚舉題。

4. 代碼示例：

 public boolean checkPartitioning(String s) {// 1. 利? dp 處理?下所有的?串是否回?int n = s.length();boolean[][] dp = new boolean[n][n];for (int i = n - 1; i >= 0; i--)for (int j = i; j < n; j++)if (s.charAt(i) == s.charAt(j))dp[i][j] = i + 1 < j ? dp[i + 1][j - 1] : true;// 2. 枚舉第?個字符串所有的起始位置和終?位置for (int i = 1; i < n - 1; i++)for (int j = i; j < n - 1; j++)if (dp[0][i - 1] && dp[i][j] && dp[j + 1][n - 1])return true;return false;}

四、分割回文串II

1. 題目鏈接：分割回文串
2. 題目描述：

給你?個字符串 s，請你將 s 分割成?些?串，使每個子串都是回文。 返回符合要求的最少分割次數 。
示例 1：輸入：s = “aab” 輸出：1
解釋：只需?次分割就可將 s 分割成 [“aa”,“b”] 這樣兩個回??串。
示例 2：輸入：s = “a” 輸出：0
示例 3：輸入：s = “ab” 輸出：1

3. 解法（動態規劃）：
   算法思路：
   狀態表?： 根據「經驗」，繼續嘗試用 i 位置為結尾，定義狀態表示，看看能否解決問題：
   dp[i] 表?： s 中 [0, i] 區間上的字符串，最少分割的次數。
   狀態轉移?程： 狀態轉移?程?般都是根據「最后?個位置」的信息來分析：設 0 <= j <= i ，那么我們可以 根據 j ~ i 位置上的?串是否是回?串分成下面兩類：
   i. 當 [j ,i] 位置上的?串能夠構成?個回文串，那么 dp[i] 就等于 [0, j - 1] 區 間上最少回文串的個數 + 1，即 dp[i] = dp[j - 1] + 1 ；
   ii. 當 [j ,i] 位置上的子串不能構成?個回文串，此時 j 位置就不用考慮。 由于我們要的是最?值，因此應該循環遍歷?遍 j 的取值，拿到里面的最小值即可。 優化：我們在狀態轉移方程里面分析到，要能夠快速判讀字符串里面的子串是否回文。因此，我們 可以先處理?個 dp 表，里面保存所有子串是否回文的信息。
   初始化： 觀察「狀態轉移方程」，我們會用到 j - 1 位置的值。我們可以思考?下當 j == 0 的時候， 表?的區間就是 [0, i] 。如果 [0, i] 區間上的字符串已經是回文串了，最?的回?串就是 1 了， j 往后的值就不?遍歷了。 因此，我們可以在循環遍歷 j 的值之前處理 j == 0 的情況，然后 j 從 1 開始循環。 但是，為了防止求 min 操作時， 0 干擾結果。我們先把表里面的值初始化為「無窮大」。
   填表順序： 毫無疑問是「從左往右」。
   返回值： 根據「狀態表示」，應該返回 dp[n - 1]

4. 代碼示例：

 public int minCut(String s) {// 1. 預處理int n = s.length();boolean[][] isPal = new boolean[n][n];for (int i = n - 1; i >= 0; i--)for (int j = i; j < n; j++)if (s.charAt(i) == s.charAt(j))isPal[i][j] = i + 1 < j ? isPal[i + 1][j - 1] : true;int[] dp = new int[n];for (int i = 0; i < n; i++) dp[i] = Integer.MAX_VALUE;for (int i = 0; i < n; i++) {if (isPal[0][i]) dp[i] = 0;else {for (int j = 1; j <= i; j++)if (isPal[j][i])dp[i] = Math.min(dp[i], dp[j - 1] + 1);}}return dp[n - 1];}

五、最長回文子序列

1. 題目鏈接：最長回文子序列
2. 題目描述：

給你?個字符串 s ，找出其中最長的回文子序列，并返回該序列的長度。 子序列定義為：不改變剩余字符順序的情況下，刪除某些字符或者不刪除任何字符形成的?個序列。
示例 1：輸入：s = “bbbab” 輸出：4 解釋：?個可能的最長回文子序列為 “bbbb” 。
示例 2：輸入：s = “cbbd” 輸出：2 解釋：?個可能的最長回文子序列為 “bb” 。

3. 解法（動態規劃）：
   算法思路：
   狀態表示： 關于「單個字符串」問題中的「回文子序列」，或者「回文子串」，我們的狀態表?研究的對象? 般都是選取原字符串中的?段區域 [i, j] 內部的情況。這里我們繼續選取字符串中的?段區域 來研究：
   dp[i][j] 表示：s 字符串 [i, j] 區間內的所有的?序列中，最長的回文子序列的長度。
   狀態轉移?程： 關于「回文子序列」和「回文子串」的分析方式，?般都是比較固定的，都是選擇這段區域的「左 右端點」的字符情況來分析。因為如果?個序列示回文串的話，「去掉首尾兩個元素之后依舊是回文串」，「?尾加上兩個相同的元素之后也依舊是回文串」。因為，根據「首尾元素」的不同，可以分為下面兩種情況：
   i. 當?尾兩個元素「相同」的時候，也就是 s[i] == s[j] ：那么 [i, j] 區間上的最長回文子序列，應該是 [i + 1, j - 1] 區間內的那個最長回文子序列首尾填上=s[i] 和 s[j] ，此時 dp[i][j] = dp[i + 1][j - 1] + 2
   ii. 當首尾兩個元素不「相同」的時候，也就是 s[i] != s[j] ：此時這兩個元素就不能同 時添加在?個回文串的左右，那么我們就應該讓 s[i] 單獨加在?個序列的左邊，或者 讓 s[j] 單獨放在?個序列的右邊，看看這兩種情況下的最大值：
   ? 單獨加入 s[i] 后的區間在 [i, j - 1] ，此時最長的回文序列的長度就是 dp[i]
   [j - 1] ；
   ? 單獨加? s[j] 后的區間在 [i + 1, j] ，此時最長的回文序列的長度就是 dp[i + 1][j] ； 取兩者的最?值，于是 dp[i][j] =max(dp[i][j - 1], dp[i + 1][j])
   綜上所述，狀態轉移?程為：
   ? 當 s[i] == s[j] 時： dp[i][j] = dp[i + 1][j - 1] + 2
   ? 當 s[i] != s[j] 時： dp[i][j] = max(dp[i][j - 1], dp[i + 1][j])
   初始化： 我們的初始化?般就是為了處理在狀態轉移的過程中，遇到的?些邊界情況，因為我們需要根據狀 態轉移?程來分析哪些位置需要初始化。 根據狀態轉移?程 dp[i][j] = dp[i + 1][j - 1] + 2 ，我們狀態表?的時候，選取的是?段區間，因此需要要求左端點的值要小于等于右端點的值，因此會有兩種邊界情況：
   i. 當 i == j 的時候， i + 1 就會大于 j - 1 ，此時區間內只有?個字符。這個比較好 分析， dp[i][j] 表示?個字符的最?回?序列，?個字符能夠自己組成回文串，因此此
   時 dp[i][j] = 1 ；
   ii. 當 i + 1 == j 的時候， i + 1 也會大于 j - 1 ，此時區間內有兩個字符。這樣也好分析，當這兩個字符相同的時候， dp[i][j] = 2 ；不相同的時候， d[i][j] = 0 。 對于第?種邊界情況，我們在填表的時候，就可以同步處理。 對于第?種邊界情況， dp[i + 1][j - 1] 的值為 0 ，不會影響最終的結果，因此可以不用考慮。
   填表順序： 根據「狀態轉移」，我們發現，在 dp 表所表示的矩陣中， dp[i + 1] 表示下?行的位置，
   dp[j - 1] 表示前?列的位置。因此我們的填表順序應該是「從下往上填寫每?行」，「每?行從左往右」。
   這個與我們?般的填寫順序不太?致。
   返回值： 根據「狀態表示」，我們需要返回 [0, n -1] 區域上的最長回文序列的長度，因此需要返回dp[0][n - 1] 。

4. 代碼示例：

public int longestPalindromeSubseq(String s) {// 1. 創建 dp 表// 2. 初始化// 3. 填表// 4. 返回結果int n = s.length();int[][] dp = new int[n][n];for (int i = n - 1; i >= 0; i--) {dp[i][i] = 1;for (int j = i + 1; j < n; j++)if (s.charAt(i) == s.charAt(j)) dp[i][j] = dp[i + 1][j - 1] + 2;else dp[i][j] = Math.max(dp[i][j - 1], dp[i + 1][j]);}return dp[0][n - 1];}

六、讓字符串成為回文串的最小插入次數

1. 題目鏈接： 讓字符串成為回文串的最小插入次數
2. 題目描述：

給你?個字符串 s ，每?次操作你都可以在字符串的任意位置插?任意字符。 請你返回讓 s 成為回?串的 最少操作次數 。 「回?串」是正讀和反讀都相同的字符串。
示例 1： 輸?：s = “zzazz” 輸出：0
解釋：字符串 “zzazz” 已經是回?串了，所以不需要做任何插?操作。
示例 2： 輸入：s = “mbadm” 輸出：2 解釋：字符串可變為 “mbdadbm” 或者 “mdbabdm” 。
示例 3： 輸入：s = “leetcode”
輸出：5 解釋：插入 5 個字符后字符串變為 “leetcodocteel” 。 提?： 1 <= s.length <= 500
s 中所有字符都是小寫字母。

3. 解法（動態規劃）： 算法思路：
   狀態表?： 關于「單個字符串」問題中的「回文子序列」，或者「回文子串」，我們的狀態表?研究的對象? 般都是選取原字符串中的?段區域 [i, j] 內部的情況。這里我們繼續選取字符串中的?段區域來研究： 狀態表示： dp[i][j] 表?字符串 [i, j] 區域成為回文子串的最少插入次數。
   狀態轉移方程： 關于「回文子序列」和「回文子串」的分析方式，?般都是比較固定的，都是選擇這段區域的「左右端點」的字符情況來分析。因為如果?個序列是回文串的話，「去掉首尾兩個元素之后依舊是回文串」，「首尾加上兩個相同的元素之后也依舊是回文串」。因為，根據「首尾元素」的不同，可以分為下面兩種情況：
   i. 當?尾兩個元素「相同」的時候，也就是 s[i] == s[j] ：
   那么 [i, j] 區間內成為回??串的最少插入次數，取決于 [i + 1, j - 1] 區間 內成為回??串的最少插入次數；
   若 i == j 或 i == j - 1 （ [i + 1, j - 1] 不構成合法區間），此時只有 1 ~ 2 個相同的字符， [i, j] 區間?定是回??串，成為回??串的最少插?次數是 0。 此時 dp[i][j] = i >= j - 1 ? 0 : dp[i + 1][j - 1] ；
   ii. 當?尾兩個元素「不相同」的時候，也就是 s[i] != s[j] ：
   此時可以在區間最右邊補上?個 s[i] ，需要的最少插?次數是 [i + 1, j] 成為回文子串的最少插入次數 + 本次插?，即 dp[i][j] = dp[i + 1][j] + 1 ；
   此時可以在區間最左邊補上?個 s[j] ，需要的最少插?次數是 [i, j + 1] 成為回文子串的最少插入次數 + 本次插?，即 dp[i][j] = dp[i][j + 1] + 1 ； 綜上所述，狀態轉移?程為：
   ? 當 s[i] == s[j] 時： dp[i][j] = i >= j - 1 ? 1 : dp[i + 1][j - 1];
   ? 當 s[i] != s[j] 時： dp[i][j] = min(dp[i + 1][j], dp[i][j - 1]) + 1 。
   初始化： 根據「狀態轉移方程」，沒有不能遞推表示的值。無需初始化。
   填表順序： 根據「狀態轉移」，我們發現，在 dp 表所表示的矩陣中， dp[i + 1] 表示下一行的位置，
   dp[j - 1] 表示前?列的位置。因此我們的填表順序應該是「從下往上填寫每一行」，「每一行從左往右」。
   這個與我們?般的填寫順序不太?致。
   返回值： 根據「狀態表示」，我們需要返回 [0, n -1] 區域上成為回文子串的最少插入次數，因此需要返回 dp[0][n - 1] 。

4. 代碼示例：

public int minInsertions(String s) {int n = s.length();int[][] dp = new int[n][n]; // 創建 dp 表for (int i = n - 1; i >= 0; i--)for (int j = i + 1; j < n; j++)if (s.charAt(i) == s.charAt(j)) dp[i][j] = dp[i + 1][j - 1];else dp[i][j] = Math.min(dp[i][j - 1], dp[i + 1][j]) + 1;return dp[0][n - 1];}

結語

本文到這里就結束了，主要通過幾道回文子串算法題，介紹了這種類型動態規劃的做題思路，帶大家深入了解了動態規劃中回文子串算法這一類型。

以上就是本文全部內容，感謝各位能夠看到最后，如有問題，歡迎各位大佬在評論區指正，希望大家可以有所收獲！創作不易，希望大家多多支持！

最后，大家再見！祝好！我們下期見！