1312. Minimum Insertion Steps to Make a String Palindrome

https://leetcode.com/problems/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]。

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];
    }
};