1312. 让字符串成为回文串的最少插入次数（动态规划）

青旅半醒 2023-10-05 19:27 16阅读 0赞

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

*  题目
 *  解题思路
 *  代码

## 题目 ##

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

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

「回文串」是正读和反读都相同的字符串。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5_size_16_color_FFFFFF_t_70]

## 解题思路 ##

和`516. 最长回文子序列`思路很相似。还是用一个二维dp数组来解决问题。  
dp数组定义：**对于s\[i…j\]，最少需要插入dp\[i\]\[j\]次才能变成回文串**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5_size_16_color_FFFFFF_t_70 1]

**base case：** 单个字符本身就是回文串，所需操作为0次

然后分两种情况

*  s.charAt(i) == s.charAt(j)  
    相等 无需操作
 *  s.charAt(i) != s.charAt(j)  
    不等，令`s[i,...,j-1]`或者`s[i+1,....,j]`成回文串，看那个需要的操作次数少

## 代码 ##

class Solution {
        
        public int minInsertions(String s) {
        
            int n=s.length();
            /*
            dp:对于s[i..j]，最少需要插入dp[i][j]次才能变成回文串
            dp默认被0填充，这里面包含了base case：i==j，单个字符本身就是回文串，所需操作为0次
            */
            int[][] dp=new int[n][n];
    
            for(int i=n-2;i>=0;i--){
        
                for(int j=i+1;j<n;j++){
        
                    if(s.charAt(i) == s.charAt(j)){
        
                        //dp[i+1][j-1]：看成子串首部尾部各一个指针，都往中间移动
                        dp[i][j]=dp[i+1][j-1];//无需操作
                    }else{
        
                        /*dp[i+1][j]：把s[i+1,..,j]变成回文串的代价
                            最后还要+1的原因：
                                假如令s[i,...,j-1]成了回文串，那么只需要在s[i,...,j-1]
                                的左边插入一个s[j]，就一定可以把s[i..j]变成回文串
                        */
                        dp[i][j]=Math.min(dp[i+1][j],dp[i][j-1])+1;
                    }
                }
    
            }
    
        return dp[0][n-1];
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20210207234254987.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/2021020723453566.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5,size_16,color_FFFFFF,t_70