【DP】以最小插入次数构造回文子串

本文正在参加「Java主题月 – Java 刷题打卡」，详情查看活动链接

一、题目概述

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

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

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

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

示例 1：

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

输入：s = "mbadm"
输出：2
解释：字符串可变为 "mbdadbm" 或者 "mdbabdm" 。
示例 3：

输入：s = "leetcode"
输出：5
解释：插入 5 个字符后字符串变为 "leetcodocteel" 。
示例 4：

输入：s = "g"
输出：0
示例 5：

输入：s = "no"
输出：1
复制代码

提示：

1 <= s.length <= 500
s 中所有字符都是小写字母。

题干分析

要找最少的插入次数，那肯定要穷举喽。

每次都可以在两个字符的中间插入任意一个字符，外加判断字符串是否为回文字符串，它的时间复杂度肯定暴增，而且是指数级的。

动态规划标准套路：

第一步要明确：状态和选择
第二步要明确：dp 数组的定义
第三步：根据 “选择”，思考状态转移的逻辑

1. 第一步要明确：状态和选择

状态：“指针 i” 和 “指针 j”

选择：“插入” 或者 “不插入”

2. 第二步要明确：dp 数组的定义

dp数组的定义：dp[i][j] , 对字符串 s[i..j]，最少需要进行 dp[i][j] 次插入才能变成回文串。

最终答案：dp[0][n - 1] 的大小（n 为 s 的长度）

base case： 当 i == j 时，dp[i][j] = 0, 因为当 i == j 时 s[i..j] 就是一个字符，本身就是回文串，所以不需要进行任何插入操作;

3. 第三步：根据 “选择”，思考状态转移的逻辑

如果 s[i] == s[j]，不需要进行任何插入，只要知道如何把 s[i+1..j-1] 变成回文串即可

如果 s[i] != s[j]，分情况讨论，看下文。

分析第三步：状态转移方程

想要计算 dp[i][j] 的值，能从子问题 dp[i + 1][j - 1] 推出 dp[i][j] 值嘛？

dp-最小插入次数2.png

也就认为 s[i+1 .. j-1] 已经是一个回文串了，所以通过 dp[i+1][j-1] 推导 dp[i][j] 的关键在于 s[i] 和 s[j]。

如果 s[i] == s[j]，不需要进行任何插入，只要知道如何把 s[i+1..j-1] 变成回文串即可。

如图：

// 翻译成代码
if (s[i] == s[j]) {
    dp[i][j] = dp[i + 1][j - 1];
}
复制代码

如果 s[i] != s[j]，分情况讨论：

当 s[i] != s[j] 时，插入两次肯定可以让 s[i..j] 变成回文串，但是不一定是插入次数最少的。

如图：

第一步：将 s[i] 插到 s[j] 的左边

第二步：将 s[j] 插到 s[i] 的左边

dp-最小插入次数3.png

特殊情况：

只需要插入一个字符即可使得 s[i..j] 变成回文，如下图：

这种情况，s[i+1..j] 或 s[i..j - 1] 原本就是回文串，那么就不需要插入，只需要插入另一个即可。

if (s[i] != s[j]) {
    // 步骤一选择代价较小的
    // 步骤二必然要进行一次插入
    dp[i][j] = Math.min(dp[i + 1][j], dp[i][j - 1]) + 1;
}
复制代码

二、思路实现

状态转移方程中 dp[i][j] 和 dp[i + 1][j] 、dp[i][j - 1]、dp[i + 1][j - 1] 三个状态有关，为了保证每次计算 dp[i][j] 时，这三个状态都已经被计算，一般选择从下向上，从左到右遍历 dp 数组：

dp-最小插入次数1.png

public class LeetCode_1312 {

    // Time: O(n ^ 2), Space: O(n ^ 2), Faster: 60.65%
    public int minInsertions(String s) {
        int n = s.length();

        // 定义： 对 s[i..j], 最少需要插入 dp[i][j] 次才能变成回文串
        // base case： dp 数组全部初始化为 0
        int [][] dp = new int[n][n];

        // 从下向上遍历
        for (int i = n - 2; i >= 0; --i) {
            // 从左向右遍历
            for (int j = i + 1; j < n; ++j) {
                // 根据 s[i] 和 s[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;
                }
            }
        }
        // 根据 dp 数组的定义，题目要求的答案是 dp[0][n - 1]
        return dp[0][n - 1];
    }
}
复制代码

优化：

dp 数组的状态只和和它相邻的状态有关，所以 dp 数组是可以压缩成一维的。

public class LeetCode_1312 {

    // Time: O(n ^ 2), Space: O(n), Faster: 77.81%
    public int minInsertions(String s) {
        int n = s.length();

        int [] dp = new int[n];

        int temp = 0;
        for (int i = n - 2; i >= 0; --i) {
            // 记录 dp[i+1][j-1]
            int pre = 0;
            for (int j = i + 1; j < n; ++j) {
                temp = dp[j];

                if (s.charAt(i) == s.charAt(j)) {
                    // dp[i][j] = dp[i+1][j-1];
                    dp[j] = pre;
                } else {
                    // dp[i][j] = Math.min(dp[i + 1][j], dp[i][j - 1]) + 1;
                    dp[j] = Math.min(dp[j], dp[j - 1]) + 1;
                }
                pre = temp;
            }
        }

        return dp[n - 1];
    }
}
复制代码