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

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

• 题目
• 解题思路
• 代码

题目

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

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

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

解题思路

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

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