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

给定一个非负整数 x ，计算并返回 x 的平方根，即实现 int sqrt(int x) 函数。

正数的平方根有两个，只输出其中的正数平方根。

如果平方根不是整数，输出只保留整数的部分，小数部分将被舍去。

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/jJ0w9p

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution {
    public int minInsertions(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        int[][] dp = new int[s.length()][s.length()];
        for (int i = 0; i < s.length() - 1; ++i) {
            if (s.charAt(i) != s.charAt(i + 1)) {
                dp[i][i + 1] = 1;
            }
        }

        for (int i = s.length() - 1; i >= 0; --i) {
            for (int j = i + 2; j < s.length(); ++j) {
                if (s.charAt(i) == s.charAt(j)) {
                    dp[i][j] = dp[i + 1][j - 1];
                } else {
                    dp[i][j] = Math.min(dp[i + 1][j], dp[i][j - 1]) + 1;
                }
            }
        }

        return dp[0][s.length() - 1];
    }
}
           

心之所向，素履以往 生如逆旅，一苇以航