📝前言說明：

• 本專欄主要記錄本人的動態規劃算法學習以及LeetCode刷題記錄，按專題劃分
• 每題主要記錄：（1）本人解法 + 本人屎山代碼；（2）優質解法 + 優質代碼；（3）精益求精，更好的解法和獨特的思想（如果有的話）
• 文章中的理解僅為個人理解。如有錯誤，感謝糾錯

🎬個人簡介：努力學習ing
📋本專欄：C++刷題專欄
📋其他專欄：C語言入門基礎，python入門基礎，C++學習筆記，Linux
🎀CSDN主頁 愚潤澤

你可以點擊下方鏈接，進行不同專題的動態規劃的學習

點擊鏈接	開始學習
斐波那契數列模型	路徑問題
簡單多狀態（一）	簡單多狀態（二）
子數組系列（一）	子數組系列（二）
子序列問題（一）	子序列問題（二）
回文串（一）	回文串（二）
兩個數組dp問題（一）	兩個數組的dp問題（二）
01背包問題	完全背包
二維的背包問題	其他

題單匯總鏈接：點擊 → 題單匯總

---

132. 分割回文串 II

題目鏈接：https://leetcode.cn/problems/palindrome-partitioning-ii/description/

---

優質解

思路：

• 對表示是否是回文子串的 isPal 數組再做一次 dp
• dp[i]: s[0 - i] 中要分割的最少次數
• 我們可以把串分成：[0 - j-1] 和 [j - i]，而 dp[j - 1] 可以表示以 j - 1 結尾的子串分割的最小次數（已知）
• 所以 j 遍歷：1 <= j <= i,
  • 如果 [j - i] 可以構成回文串: dp[i] = dp[j - 1] + 1,
  • 不能構成: 跳過(遲早到 i == j 的時候會構成回文)
  • 取循環中得到的 dp[i] 的最小值

代碼：

class Solution {
public:int minCut(string s) {int n = s.size();vector<vector<bool>> isPal(n, vector<bool>(n, 0));for(int i = n - 1; i >= 0; i--){for(int j = i; j < n; j++){if(s[i] == s[j])isPal[i][j] = i + 1 < j ? isPal[i + 1][j - 1] : true;}}// 對 isPal 做 dpvector<int> dp(n, INT_MAX / 2);for(int i = 0; i < n; i++){if(isPal[0][i]) dp[i] = 0; // 判斷 0 - ielse{for(int j = 1; j <= i; j++){if(isPal[j][i])dp[i] = min(dp[i], dp[j - 1] + 1);}}}return dp[n - 1];}
};

時間復雜度：$O(n^2)$
空間復雜度：$O(n^2)$

---

516. 最長回文子序列

題目鏈接：https://leetcode.cn/problems/longest-palindromic-subsequence/description/

---

優質解

思路

狀態表示

• dp[i][j]: [i, j]區間內的所有子序列中，最長的回文子序列

狀態轉移方程

• if s[i] == s[j], 那 dp[i][j] = dp[i + 1][j - 1] + 1;
  • 無效區間(越界), i + 1 < j : dp[i][i] = 字符個數;
• if s[i] != s[j] (代表兩端不會同時對構成回文子序列有幫助)
  • 去[i + 1, j] 和 [i, j - 1] 兩個區間找: max(dp[i][j - 1], dp[i + 1][j]);

初始化:

• 發現只有[0][0] 和 [i - 1][i - 1] 會越界(但是狀態轉移方程已經處理了)
  填表順序

填表順序

• 看狀態轉移需要什么位置的 dp 值
  • 整體行: 從下到上(因為需要 i - 1),
  • 每一行內部: 從左往右(因為要 j - 1)

返回值

• dp[0][n - 1];

代碼：

class Solution {
public:int longestPalindromeSubseq(string s) {int n = s.size();vector<vector<int>> dp(n, vector<int>(n, 0));for(int i = n - 1; i >= 0; i--){dp[i][i] = 1; // 初始化for(int j = i + 1; j < n; j++) // 枚舉右端{if(s[i] == s[j])dp[i][j] = i + 1 == j ? 2 : dp[i + 1][j - 1] + 2;else dp[i][j] = max(dp[i][j - 1], dp[i + 1][j]);}}return dp[0][n - 1];}
};

時間復雜度：$O(n^2)$
空間復雜度：$O(n^2)$

---

1312. 讓字符串成為回文串的最少插入次數

題目鏈接：https://leetcode.cn/problems/minimum-insertion-steps-to-make-a-string-palindrome/description/

---

優質解

思路：

• 總體思路和上一題都差不多
• 狀態表示：dp[i][j]：[i, j]區間的子串，成為回文串的最小插入次數
• 狀態轉移方程：s[i] == s[j]...不多說了，s[i] != s[j]...
• 細節問題不說了

代碼：

class Solution {
public:int minInsertions(string s) {int n = s.size();vector<vector<int>> dp(n, vector<int>(n, INT_MAX));for(int i = n - 1; i >= 0; i--){dp[i][i] = 0;for(int j = i + 1; j < n; j++){if(s[i] == s[j])dp[i][j] = i + 1 == j? 0 : dp[i + 1][j - 1];elsedp[i][j] = min(dp[i + 1][j], dp[i][j - 1]) + 1;}}return dp[0][n - 1];}
};

時間復雜度：$O(n^2)$
空間復雜度：$O(n^2)$

---

🌈我的分享也就到此結束啦🌈
要是我的分享也能對你的學習起到幫助，那簡直是太酷啦！
若有不足，還請大家多多指正，我們一起學習交流！
📢公主，王子：點贊👍→收藏?→關注🔍
感謝大家的觀看和支持！祝大家都能得償所愿，天天開心！！！