[数据结构与算法]leetcode 1312. 让字符串成为回文串的最少插入次数 (区间DP）

题目描述
给你一个字符串 s ，每一次操作你都可以在字符串的任意位置插入任意字符。请你返回让 s 成为回文串的 最少操作次数 。「回文串」是正读和反读都相同的字符串。

示例 1：
输入：s = “zzazz”
输出：0
解释：字符串 “zzazz” 已经是回文串了，所以不需要做任何插入操作。
示例 2：
输入：s = “mbadm”
输出：2
解释：字符串可变为 “mbdadbm” 或者 “mdbabdm” 。
示例 3：
输入：s = “leetcode”
输出：5
解释：插入 5 个字符后字符串变为 “leetcodocteel” 。
示例 4：
输入：s = “g”
输出：0
示例 5：
输入：s = “no”
输出：1

区间DP的模板，依次枚举起点和终点，dp[i][j] 表示区间i~j之间的操作次数，如果s[i]==s[j] 那么操作次数就取决于 i+1 ~ j-1 之间字符串的操作次数，如果二者不相等，那么就取决于[i+1,j] 和[i,j-1] 这两个区间次数的最小值加1

class Solution {
public:
    int minInsertions(string s) {
        int n = s.size();
        vector<vector<int>> dp(n, vector<int>(n));
        for (int len = 2; len <= n; len++) 
        {
            for (int i = 0; i + len - 1<n; i++) 
            {
                int j = i + len - 1;
                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;
            }
        }
        return dp[0][n - 1];
    }
};

还有一种解法

class Solution {
public:
    int minInsertions(string s) {
        int n =s.size();
        vector<vector<int>> dp(n, vector<int>(n, 0));
        for(int i=n-2;i>=0;i--)
        {
            for(int j=i+1;j<n;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;
                }
            }
        }
        return dp[0][n-1];
    }
};

题目变形：360笔试题