讀完本文袜腥，你可以去力扣拿下如下題目：
-----------
回文串就是正著讀反著讀都一樣的字符见擦，在筆試面試中經(jīng)常出現(xiàn)這類問題。
labuladong 公眾號(hào)有好幾篇講解回文問題的文章羹令，是判斷回文串或者尋找最長(zhǎng)回文串/子序列的：
本文就來研究一道構(gòu)造回文串的問題鲤屡，難度 Hard 計(jì)算讓字符串成為回文串的最少插入次數(shù)：
輸入一個(gè)字符串 s，你可以在字符串的任意位置插入任意字符福侈。如果要把 s 變成回文串酒来，請(qǐng)你計(jì)算最少要進(jìn)行多少次插入？
函數(shù)簽名如下：
int minInsertions(string s);
比如說輸入 s = "abcea"肪凛，算法返回 2堰汉，因?yàn)榭梢越o s 插入 2 個(gè)字符變成回文串 "abeceba" 或者 "aebcbea"辽社。如果輸入 s = "aba"，則算法返回 0翘鸭，因?yàn)?s 已經(jīng)是回文串滴铅，不用插入任何字符。
思路解析
首先就乓，要找最少的插入次數(shù)汉匙，那肯定得窮舉嘍，如果我們用暴力算法窮舉出所有插入方法档址，時(shí)間復(fù)雜度是多少盹兢？
每次都可以在兩個(gè)字符的中間插入任意一個(gè)字符，外加判斷字符串是否為回文字符串守伸，這時(shí)間復(fù)雜度肯定爆炸绎秒，是指數(shù)級(jí)。
那么無疑尼摹，這個(gè)問題需要使用動(dòng)態(tài)規(guī)劃技巧來解決见芹。之前的文章說過，回文問題一般都是從字符串的中間向兩端擴(kuò)散蠢涝，構(gòu)造回文串也是類似的玄呛。
我們定義一個(gè)二維的 dp 數(shù)組，dp[i][j] 的定義如下：對(duì)字符串 s[i..j]和二，最少需要進(jìn)行 dp[i][j] 次插入才能變成回文串徘铝。
我們想求整個(gè) s 的最少插入次數(shù)，根據(jù)這個(gè)定義惯吕，也就是想求 dp[0][n-1] 的大刑杷（n 為 s 的長(zhǎng)度）。
同時(shí)废登，base case 也很容易想到淹魄，當(dāng) i == j 時(shí) dp[i][j] = 0，因?yàn)楫?dāng) i == j 時(shí) s[i..j] 就是一個(gè)字符堡距，本身就是回文串甲锡，所以不需要進(jìn)行任何插入操作。
接下來就是動(dòng)態(tài)規(guī)劃的重頭戲了羽戒，利用數(shù)學(xué)歸納法思考狀態(tài)轉(zhuǎn)移方程缤沦。
PS：我認(rèn)真寫了 100 多篇原創(chuàng)，手把手刷 200 道力扣題目易稠，全部發(fā)布在 labuladong的算法小抄疚俱，持續(xù)更新。建議收藏缩多，按照我的文章順序刷題呆奕，掌握各種算法套路后投再入題海就如魚得水了。
狀態(tài)轉(zhuǎn)移方程
狀態(tài)轉(zhuǎn)移就是從小規(guī)模問題的答案推導(dǎo)更大規(guī)模問題的答案衬吆，從 base case 向其他狀態(tài)推導(dǎo)嘛梁钾。如果我們現(xiàn)在想計(jì)算 dp[i][j] 的值，而且假設(shè)我們已經(jīng)計(jì)算出了子問題 dp[i+1][j-1] 的值了逊抡，你能不能想辦法推出 dp[i][j] 的值呢姆泻？
既然已經(jīng)算出 dp[i+1][j-1]冒嫡，即知道了 s[i+1..j-1] 成為回文串的最小插入次數(shù)，那么也就可以認(rèn)為 s[i+1..j-1] 已經(jīng)是一個(gè)回文串了方咆，所以通過 dp[i+1][j-1] 推導(dǎo) dp[i][j] 的關(guān)鍵就在于 s[i] 和 s[j] 這兩個(gè)字符蟀架。
這個(gè)得分情況討論，如果 s[i] == s[j] 的話煌集，我們不需要進(jìn)行任何插入捌省，只要知道如何把 s[i+1..j-1] 變成回文串即可：
翻譯成代碼就是這樣：
if (s[i] == s[j]) {
dp[i][j] = dp[i + 1][j - 1];
}
如果 s[i] != s[j] 的話，就比較麻煩了卷拘，比如下面這種情況：
最簡(jiǎn)單的想法就是色徘，先把 s[j] 插到 s[i] 右邊，同時(shí)把 s[i] 插到 s[j] 右邊横腿，這樣構(gòu)造出來的字符串一定是回文串：
PS：當(dāng)然斤寂，把 s[j] 插到 s[i] 左邊，然后把 s[i] 插到 s[j] 左邊也是一樣的罗侯，后面會(huì)分析。
但是钩杰，這是不是就意味著代碼可以直接這樣寫呢？
if (s[i] != s[j]) {
// 把 s[j] 插到 s[i] 右邊措左，把 s[i] 插到 s[j] 右邊
dp[i][j] = dp[i + 1][j - 1] + 2;
}
不對(duì)避除，比如說如下這兩種情況，只需要插入一個(gè)字符即可使得 s[i..j] 變成回文：
所以說凉逛，當(dāng) s[i] != s[j] 時(shí)群井，無腦插入兩次肯定是可以讓 s[i..j] 變成回文串，但是不一定是插入次數(shù)最少的昔瞧，最優(yōu)的插入方案應(yīng)該被拆解成如下流程：
步驟一菩佑，做選擇，先將 s[i..j-1] 或者 s[i+1..j] 變成回文串稍坯。怎么做選擇呢？誰變成回文串的插入次數(shù)少混巧，就選誰唄勤揩。
比如圖二的情況，將 s[i+1..j] 變成回文串的代價(jià)小傍衡，因?yàn)樗旧砭褪腔匚拇喝洌静恍枰迦耄煌硇宓模瑢?duì)于圖三，將 s[i..j-1] 變成回文串的代價(jià)更小屡江。
然而盼理，如果 s[i+1..j] 和 s[i..j-1] 都不是回文串，都至少需要插入一個(gè)字符才能變成回文宏怔，所以選擇哪一個(gè)都一樣：
那我怎么知道 s[i+1..j] 和 s[i..j-1] 誰變成回文串的代價(jià)更小呢畴椰？
回頭看看 dp 數(shù)組的定義是什么，dp[i+1][j] 和 dp[i][j-1] 不就是它們變成回文串的代價(jià)么抓艳？
步驟二帚戳，根據(jù)步驟一的選擇，將 s[i..j] 變成回文偏友。
如果你在步驟一中選擇把 s[i+1..j] 變成回文串对供，那么在 s[i+1..j] 右邊插入一個(gè)字符 s[i] 一定可以將 s[i..j] 變成回文；同理产场，如果在步驟一中選擇把 s[i..j-1] 變成回文串京景，在 s[i..j-1] 左邊插入一個(gè)字符 s[j] 一定可以將 s[i..j] 變成回文。
那么根據(jù)剛才對(duì) dp 數(shù)組的定義以及以上的分析确徙，s[i] != s[j] 時(shí)的代碼邏輯如下：
if (s[i] != s[j]) {
// 步驟一選擇代價(jià)較小的
// 步驟二必然要進(jìn)行一次插入
dp[i][j] = min(dp[i + 1][j], dp[i][j - 1]) + 1;
}
綜合起來，狀態(tài)轉(zhuǎn)移方程如下：
if (s[i] == s[j]) {
dp[i][j] = dp[i + 1][j - 1];
} else {
dp[i][j] = min(dp[i + 1][j], dp[i][j - 1]) + 1;
}
這就是動(dòng)態(tài)規(guī)劃算法核心厦凤，我們可以直接寫出解法代碼了育苟。
PS：我認(rèn)真寫了 100 多篇原創(chuàng)，手把手刷 200 道力扣題目博烂，全部發(fā)布在 labuladong的算法小抄，持續(xù)更新禽篱。建議收藏，按照我的文章順序刷題玛界，掌握各種算法套路后投再入題海就如魚得水了悼吱。
代碼實(shí)現(xiàn)
首先想想 base case 是什么，當(dāng) i == j 時(shí) dp[i][j] = 0笨枯，因?yàn)檫@時(shí)候 s[i..j] 就是單個(gè)字符遇西，本身就是回文串，不需要任何插入洲敢；最終的答案是 dp[0][n-1]（n 是字符串 s 的長(zhǎng)度）梧税。那么 dp table 長(zhǎng)這樣：
又因?yàn)闋顟B(tài)轉(zhuǎn)移方程中 dp[i][j] 和 dp[i+1][j]，dp[i]-1]哮塞，dp[i+1][j-1] 三個(gè)狀態(tài)有關(guān)凳谦，為了保證每次計(jì)算 dp[i][j] 時(shí)，這三個(gè)狀態(tài)都已經(jīng)被計(jì)算家凯，我們一般選擇從下向上如失，從左到右遍歷 dp 數(shù)組：
完整代碼如下：
int minInsertions(string s) {
int n = s.size();
// 定義：對(duì) s[i..j]，最少需要插入 dp[i][j] 次才能變成回文
vector<vector<int>> dp(n, vector<int>(n, 0));
// base case：i == j 時(shí) dp[i][j] = 0掂之，單個(gè)字符本身就是回文
// dp 數(shù)組已經(jīng)全部初始化為 0世舰，base case 已初始化
// 從下向上遍歷
for (int i = n - 2; i >= 0; i--) {
// 從左向右遍歷
for (int j = i + 1; j < n; j++) {
// 根據(jù) s[i] 和 s[j] 進(jìn)行狀態(tài)轉(zhuǎn)移
if (s[i] == s[j]) {
dp[i][j] = dp[i + 1][j - 1];
} else {
dp[i][j] = min(dp[i + 1][j], dp[i][j - 1]) + 1;
}
}
}
// 根據(jù) dp 數(shù)組的定義，題目要求的答案
return dp[0][n - 1];
}
現(xiàn)在這道題就解決了跟压，時(shí)間和空間復(fù)雜度都是 O(N^2)震蒋。還有一個(gè)小優(yōu)化，注意到 dp 數(shù)組的狀態(tài)之和它相鄰的狀態(tài)有關(guān)翔横，所以 dp 數(shù)組是可以壓縮成一維的：
int minInsertions(string s) {
int n = s.size();
vector<int> dp(n, 0);
int temp = 0;
for (int i = n - 2; i >= 0; i--) {
// 記錄 dp[i+1][j-1]
int pre = 0;
for (int j = i + 1; j < n; j++) {
temp = dp[j];
if (s[i] == s[j]) {
// dp[i][j] = dp[i+1][j-1];
dp[j] = pre;
} else {
// dp[i][j] = min(dp[i+1][j], dp[i][j-1]) + 1;
dp[j] = =min(dp[j], dp[j - 1]) + 1;
}
pre = temp;
}
}
return dp[n - 1];
}
至于這個(gè)狀態(tài)壓縮是怎么做的梗搅，我們前文 狀態(tài)壓縮技巧 詳細(xì)介紹過无切，這里就不展開了丐枉。
＿＿＿＿＿＿＿＿＿＿＿＿＿
我的 在線電子書 有 100 篇原創(chuàng)文章，手把手帶刷 200 道力扣題目籍嘹，建議收藏弯院！對(duì)應(yīng)的 GitHub 算法倉庫 已經(jīng)獲得了 70k star听绳，歡迎標(biāo)星！
