1312. The minimum number of inserts to make a string a palindrome string

Give you a string s , You can insert any character in any position of the string every time .

Please return to let s To become a palindrome Minimum number of operations .

「 Palindrome string 」 It's the same string for both forward and reverse reading .

Example 1：

Input ：s = “zzazz”
Output ：0
explain ： character string “zzazz” It's already a palindrome , So you don't need to do any insertion .

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/minimum-insertion-steps-to-make-a-string-palindrome
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Answer key

Dynamic programming , Range try model
dp[i][j]:str from i To j How many characters need to be inserted to form a palindrome string
The lower left half is useless , Fill in the diagonal 0

Penultimate diagonal L==R-1
Equal is equal 0 individual , Don't wait 1 individual

General position :
dp[i][j] Yes 3 In this case

1) hypothesis i To j-1 Are already palindromes , We just need to i-1 Position plus j The characters of
dp[i][j-1]+1

2) hypothesis i+1 To j Are already palindromes , We just need to i Position plus j The characters of
namely dp[i+1][j]+1

3) hypothesis i+1 To j-1 Are already palindromes , also i And j equal
dp[i][j]

Code

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