> 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/) 详细介绍过，这里就不展开了。
---
# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.
## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter, and the optional `goal` query parameter:
```
GET https://junnie.gitbook.io/nine-chapter/9.dynamic-programming/1312.-minimum-insertion-steps-to-make-a-string-palindrome-h.md?ask=&goal=
```
`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.