# 1312. Minimum Insertion Steps to Make a String Palindrome

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".
```

**Example 4:**

```
Input: s = "g"
Output: 0
```

**Example 5:**

```
Input: s = "no"
Output: 1
```

问字符串最少插入多少字符能使它变成回文。min + 回文 => DP或KMP。DP\[i, j]表示s\[i,j]至少需要的数目，检查s\[i]是否等于s\[j]，等的时候为dp\[i+1]\[j-1]，不等时action为补s\[i]或补s\[j]。

```cpp
class Solution {
public:
    int minInsertions(string s) {
        const int N = s.length();
        vector<vector<int>> dp(N, vector<int>(N, INT_MAX));
        for (int i = 0; i < N; ++i) dp[i][i] = 0;
        for (int i = N; i >= 0; --i) {
            for (int j = i + 1; j < N; ++j) {
                if (s[i] == s[j]) {
                    dp[i][j] = j == i + 1 ? 0 : dp[i + 1][j - 1];
                } else {
                    dp[i][j] = min(dp[i + 1][j], dp[i][j - 1]) + 1;
                }
            }
        }
        return dp[0][N - 1];
    }
};
```