---

1312. 让字符串成为回文串的最少插入次数

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

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

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

示例 1：

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/minimum-insertion-steps-to-make-a-string-palindrome
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解

动态规划,范围尝试模型
dp[i][j]:str从i到j需要插入多少个字符形成回文串
左下半区没用,对角线填0

倒数第二条对角线L==R-1
相等就埴0个,不等就埴1个

普遍位置:
dp[i][j]有3种情况

1)假设i到j-1都已经是回文串,我们只需在i-1位置加上j的字符
dp[i][j-1]+1

2)假设i+1到j都已经是回文串,我们只需在i位置加上j的字符
即dp[i+1][j]+1

3)假设i+1到j-1都已经是回文串,并且i与j相等
dp[i][j]

代码

class Solution {
    public int minInsertions(String s) {
        char[] str=s.toCharArray();
        int n=str.length;
        if(n==0||n==1){
            return 0;
        }
        int[][] dp=new int[n][n];
        for(int i=0;i<n-1;i++){
            dp[i][i+1]=str[i]==str[i+1]?0:1;
        }
        for(int i=n-3;i>=0;i--){
            for(int j=i+2;j<n;j++){
                dp[i][j]=Math.min(dp[i+1][j],dp[i][j-1])+1;
                if(str[i]==str[j]){
                    dp[i][j]=Math.min(dp[i][j],dp[i+1][j-1]);
                }
            }
        }
        return dp[0][n-1];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22