> For the complete documentation index, see [llms.txt](https://junnie.gitbook.io/nine-chapter/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://junnie.gitbook.io/nine-chapter/9.dynamic-programming/1312.-minimum-insertion-steps-to-make-a-string-palindrome-h.md).
# 1312. Minimum Insertion Steps to Make a String Palindrome (H)
Given a string `s`. In one step you can insert any character at any index of the string.
Return *the minimum number of steps* to make `s` palindrome.
A **Palindrome String** is one that reads the same backward as well as forward.
**Example 1:**
```
Input: s = "zzazz"
Output: 0
Explanation: The string "zzazz" is already palindrome we don't need any insertions.
```
**Example 2:**
```
Input: s = "mbadm"
Output: 2
Explanation: String can be "mbdadbm" or "mdbabdm".
```
**Example 3:**
```
Input: s = "leetcode"
Output: 5
Explanation: Inserting 5 characters the string becomes "leetcodocteel".
```
**Constraints:**
* `1 <= s.length <= 500`
* `s` consists of lowercase English letters.
### Solution:
首先，要找最少的插入次数，那肯定得穷举喽，如果我们用暴力算法穷举出所有插入方法，时间复杂度是多少？
每次都可以在两个字符的中间插入任意一个字符，外加判断字符串是否为回文字符串，这时间复杂度肯定爆炸，是指数级。
那么无疑，这个问题需要使用动态规划技巧来解决。之前的文章说过，回文问题一般都是从字符串的中间向两端扩散，构造回文串也是类似的。
**我们定义一个二维的 `dp` 数组，`dp[i][j]` 的定义如下：对字符串 `s[i..j]`，最少需要进行 `dp[i][j]` 次插入才能变成回文串**。
我们想求整个 `s` 的最少插入次数，根据这个定义，也就是想求 `dp[0][n-1]` 的大小（`n` 为 `s` 的长度）。
同时，base case 也很容易想到，当 `i == j` 时 `dp[i][j] = 0`，因为当 `i == j` 时 `s[i..j]` 就是一个字符，本身就是回文串，所以不需要进行任何插入操作。
接下来就是动态规划的重头戏了，利用数学归纳法思考状态转移方程。
#### 状态转移方程
状态转移就是从小规模问题的答案推导更大规模问题的答案，从 base case 向其他状态推导嘛。**如果我们现在想计算 `dp[i][j]` 的值，而且假设我们已经计算出了子问题 `dp[i+1][j-1]` 的值了，你能不能想办法推出 `dp[i][j]` 的值呢**？
[](https://labuladong.gitee.io/algo/images/%e6%8f%92%e5%85%a5%e5%9b%9e%e6%96%87/1.jpeg)
既然已经算出 `dp[i+1][j-1]`，即知道了 `s[i+1..j-1]` 成为回文串的最小插入次数，**那么也就可以认为 `s[i+1..j-1]` 已经是一个回文串了，所以通过 `dp[i+1][j-1]` 推导 `dp[i][j]` 的关键就在于 `s[i]` 和 `s[j]` 这两个字符**。
[](https://labuladong.gitee.io/algo/images/%e6%8f%92%e5%85%a5%e5%9b%9e%e6%96%87/2.jpeg)
这个得分情况讨论，**如果 `s[i] == s[j]` 的话**，我们不需要进行任何插入，只要知道如何把 `s[i+1..j-1]` 变成回文串即可：
[](https://labuladong.gitee.io/algo/images/%e6%8f%92%e5%85%a5%e5%9b%9e%e6%96%87/3.jpeg)
翻译成代码就是这样：
```cpp
if (s[i] == s[j]) {
dp[i][j] = dp[i + 1][j - 1];
}
```
**如果 `s[i] != s[j]` 的话**，就比较麻烦了，比如下面这种情况：
[](https://labuladong.gitee.io/algo/images/%e6%8f%92%e5%85%a5%e5%9b%9e%e6%96%87/4.jpeg)
最简单的想法就是，先把 `s[j]` 插到 `s[i]` 右边，同时把 `s[i]` 插到 `s[j]` 右边，这样构造出来的字符串一定是回文串：
[](https://labuladong.gitee.io/algo/images/%e6%8f%92%e5%85%a5%e5%9b%9e%e6%96%87/5.jpeg)
> PS：当然，把 `s[j]` 插到 `s[i]` 左边，然后把 `s[i]` 插到 `s[j]` 左边也是一样的，后面会分析。
但是，这是不是就意味着代码可以直接这样写呢？
```cpp
if (s[i] != s[j]) {
// 把 s[j] 插到 s[i] 右边，把 s[i] 插到 s[j] 右边
dp[i][j] = dp[i + 1][j - 1] + 2;
}
```
不对，比如说如下这两种情况，只需要插入一个字符即可使得 `s[i..j]` 变成回文：
[](https://labuladong.gitee.io/algo/images/%e6%8f%92%e5%85%a5%e5%9b%9e%e6%96%87/6.jpeg)
所以说，当 `s[i] != s[j]` 时，无脑插入两次肯定是可以让 `s[i..j]` 变成回文串，但是不一定是插入次数最少的，最优的插入方案应该被拆解成如下流程：
**步骤一，做选择，先将 `s[i..j-1]` 或者 `s[i+1..j]` 变成回文串**。怎么做选择呢？谁变成回文串的插入次数少，就选谁呗。
比如图二的情况，将 `s[i+1..j]` 变成回文串的代价小，因为它本身就是回文串，根本不需要插入；同理，对于图三，将 `s[i..j-1]` 变成回文串的代价更小。
然而，如果 `s[i+1..j]` 和 `s[i..j-1]` 都不是回文串，都至少需要插入一个字符才能变成回文，所以选择哪一个都一样：
[](https://labuladong.gitee.io/algo/images/%e6%8f%92%e5%85%a5%e5%9b%9e%e6%96%87/7.jpeg)
那我怎么知道 `s[i+1..j]` 和 `s[i..j-1]` 谁变成回文串的代价更小呢？
回头看看 `dp` 数组的定义是什么，`dp[i+1][j]` 和 `dp[i][j-1]` 不就是它们变成回文串的代价么？
**步骤二，根据步骤一的选择，将 `s[i..j]` 变成回文**。
如果你在步骤一中选择把 `s[i+1..j]` 变成回文串，那么在 `s[i+1..j]` 右边插入一个字符 `s[i]` 一定可以将 `s[i..j]` 变成回文；同理，如果在步骤一中选择把 `s[i..j-1]` 变成回文串，在 `s[i..j-1]` 左边插入一个字符 `s[j]` 一定可以将 `s[i..j]` 变成回文。
那么根据刚才对 `dp` 数组的定义以及以上的分析，`s[i] != s[j]` 时的代码逻辑如下：
```cpp
if (s[i] != s[j]) {
// 步骤一选择代价较小的
// 步骤二必然要进行一次插入
dp[i][j] = min(dp[i + 1][j], dp[i][j - 1]) + 1;
}
```
综合起来，状态转移方程如下：
```cpp
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;
}
```
这就是动态规划算法核心，我们可以直接写出解法代码了。
#### 代码实现
首先想想 base case 是什么，当 `i == j` 时 `dp[i][j] = 0`，因为这时候 `s[i..j]` 就是单个字符，本身就是回文串，不需要任何插入；最终的答案是 `dp[0][n-1]`（`n` 是字符串 `s` 的长度）。那么 dp table 长这样：
[](https://labuladong.gitee.io/algo/images/%e6%8f%92%e5%85%a5%e5%9b%9e%e6%96%87/8.jpeg)
又因为状态转移方程中 `dp[i][j]` 和 `dp[i+1][j]`，`dp[i]-1]`，`dp[i+1][j-1]` 三个状态有关，为了保证每次计算 `dp[i][j]` 时，这三个状态都已经被计算，我们一般选择从下向上，从左到右遍历 `dp` 数组：
[](https://labuladong.gitee.io/algo/images/%e6%8f%92%e5%85%a5%e5%9b%9e%e6%96%87/9.jpeg)
完整代码如下：
```cpp
int minInsertions(string s) {
int n = s.size();
// 定义：对 s[i..j]，最少需要插入 dp[i][j] 次才能变成回文
vector> dp(n, vector(n, 0));
// base case：i == j 时 dp[i][j] = 0，单个字符本身就是回文
// dp 数组已经全部初始化为 0，base case 已初始化
// 从下向上遍历
for (int i = n - 2; i >= 0; i--) {
// 从左向右遍历
for (int j = i + 1; j < n; j++) {
// 根据 s[i] 和 s[j] 进行状态转移
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;
}
}
}
// 根据 dp 数组的定义，题目要求的答案
return dp[0][n - 1];
}
```
现在这道题就解决了，时间和空间复杂度都是 O(N^2)。还有一个小优化，注意到 `dp` 数组的状态之和它相邻的状态有关，所以 `dp` 数组是可以压缩成一维的：
```cpp
int minInsertions(string s) {
int n = s.size();
vector 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];
}
```
至于这个空间优化是怎么做的，我们前文 [空间压缩技巧](https://labuladong.gitee.io/algo/3/23/75/) 详细介绍过，这里就不展开了。