【区间dp-回文子序列-8-1】leet 1312. 让字符串成为回文串的最少插入次数

给你一个字符串 s ，每一次操作你都可以在字符串的任意位置插入任意字符。

请你返回让 s 成为回文串的 最少操作次数 。

「回文串」是正读和反读都相同的字符串。

示例 1：

输入：s = "zzazz"
输出：0
解释：字符串 "zzazz" 已经是回文串了，所以不需要做任何插入操作。

示例 2：

输入：s = "mbadm"
输出：2
解释：字符串可变为 "mbdadbm" 或者 "mdbabdm" 。

示例 3：

输入：s = "leetcode"
输出：5
解释：插入 5 个字符后字符串变为 "leetcodocteel" 。

提示：

• 1 <= s.length <= 500
• s 中所有字符都是小写字母。

【题解manacher-2】最短回文串-末尾增加字符 只允许在字符串末尾添加字符，使字符串变成最短的回文字符串

【题解manacher-3】leet214 最短回文串--前面增加字符。只允许在字符串前面添加字符，使字符串变成最短的回文字符串

本题是在字符串的任何位置添加字符，是字符串变成最短的回文字符串

题解一：

本题只要给出最少操作次数，由上一题【区间dp-回文子序列-7】leet 516. 最长回文子序列 可以知道，构成的最长回文子序列长度是dp[0][n-1]，如果把没有构成回文子序列的字符补充到以子序列中心为中心的对应位置，则可以用增加最少的字符获取到回文字符串。所以答案是n-dp[0][n-1].

      public int minInsertions(String str) {
        char[] s = str.toCharArray();
        int n = s.length;
        int[][] dp = new int[n][n];
        for (int r = 0; r < n; r++) {
            for (int l = r; l >= 0; l--) {
                if (l == r) dp[l][r] = 1;
                else {
                    if (s[l] == s[r]) dp[l][r] = dp[l + 1][r - 1] + 2;
                    else dp[l][r] = Math.max(dp[l + 1][r], dp[l][r - 1]);
                }
            }
        }

        return n-dp[0][n-1];
    }

当然这个题目也可以不用最长子序列的结果。

题解二：

dp[l][r]就是在区间[l,r]之内，题目要求的---让字符串s[l,r]成为回文串的最少插入次数。则有如下递推公式：

dp[l][r]=dp[l + 1][r - 1]. 条件：s[l]==s[r]

dp[l][r] = Math.min(dp[l + 1][r], dp[l][r - 1]) + 1 条件：s[l]!=s[r]

dp[l][r] = 0，初始条件l==r

所以也 可以如下方式解决：

      public int minInsertions(String str) {
        char[] s = str.toCharArray();
        int n = s.length;
        int[][] dp = new int[n][n];
        for (int r = 0; r < n; r++) {
            for (int l = r; l >= 0; l--) {
                if (l == r) dp[l][r] = 0;
                else {
                    if (s[l] == s[r]) dp[l][r] = dp[l + 1][r - 1] ;
                    else dp[l][r] = Math.min(dp[l + 1][r], dp[l][r - 1]) + 1;
                }
            }
        }

        return dp[0][n - 1];
    }

相似题目：

【区间dp-回文子序列-7】leet 516. 最长回文子序列

【区间dp-回文子序列-8-2】添加最少的字符让字符串变为回文字符串

【区间dp-回文子序列-8-3】添加最少的字符让字符串变为回文字符串

【区间dp-回文子序列-8-4】SH10 回文数组