1312. 让字符串成为回文串的最少插入次数：双指针记忆化搜索 or 区间 DP.md

题目简述：

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

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

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

题目链接：1312. 让字符串成为回文串的最少插入次数

双指针 + 记忆化搜索

思路

就按回溯算法的思路进行解空间的搜索即可，DFS 的形参为左指针与右指针，返回值表示从此处开始需要插入多少个字符才能使字符串成为回文串。

但要注意的是一定要记得为搜索加上记忆化缓存以剪枝，否则会造成大量重复搜索。

代码

算法的时间复杂度为 $O(n^2)$，空间复杂度为 $O(n^2)$。

代码实际执行时 HashMap 的开销很大，哈希表实现改为二维数组能够节省相当夸张的时间开销——但算法的逻辑是一致的、不变的。

class Solution {

    private Map<Long, Integer> cache;
    private String s;

    public int minInsertions(String s) {
        cache = new HashMap<>();
        this.s = s;
        return dfs(0, s.length() - 1);
    }

    private int dfs(int l, int r) {
        if (l >= r) return 0;
        Integer cacheRes = cache.get(pair(l, r));
        if (cacheRes != null) return cacheRes;

        if (s.charAt(l) != s.charAt(r)) {
            int res1 = dfs(l + 1, r);
            int res2 = dfs(l, r - 1);
            int res = 1 + Math.min(res1, res2);
            cache.put(pair(l, r), res);
            return res;
        } else {
            int res = dfs(l + 1, r - 1);
            cache.put(pair(l, r), res);
            return res;
        }
    }

    private long pair(int a, int b) {
        return ((long) a << 32) | (b & 0xFFFFFFFFL);
    }
}

区间 DP

思路

这个问题我觉得记忆化搜索比区间 DP 更直观，但既然可以自底而上地记忆化搜索，当然也可以自顶而下地 DP。在实现了双指针回溯算法的记忆化搜索后再来实现区间 DP，就是手到擒来了。

设计 $dp[i][j]$ 表示 DFS 的左指针 $i$ 与右指针 $j$ 围住的子串还需要插入多少个字符，则 $$ dp[i][j]=\left{\begin{align}&1+\min\big{dp[i+1][j],,dp[i][j-1]\big},&&s[i]\neq s[j]\\&dp[i+1][j-1],&&s[i]=s[j]\end{align}\right. $$ 初始化： $$ \forall i,\ dp[i][i]=0 $$

$$ \forall i,\ dp[i][i+1]=\left{\begin{align}&1,&&s[i]\neq s[i+1]\\&0,&&s[i]=s[i+1]\end{align}\right. $$

可以看出，外层 $i$ 循环应从下至上填表，内层 $j$ 循环应从左至右填表。而且不难推出，可以考虑滚动数组降低空间开销。

代码

算法的时间复杂度为 $O(n^2)$，空间复杂度为 $O(n)$。

区间 DP 应该是本问题的最优方案了。

class Solution {
    public int minInsertions(String s) {
        int n = s.length();
        int[] dp1 = new int[n];
        int[] dp2 = new int[n];
        // dp1[n - 1] = 0;

        for (int i = n - 2; i >= 0; i--) {
            char c = s.charAt(i);
            // dp2[i] = 0;
            dp2[i + 1] = c == s.charAt(i + 1) ? 0 : 1;

            for (int j = i + 2; j < n; j++) {
                if (c == s.charAt(j)) {
                    dp2[j] = dp1[j - 1];
                } else {
                    dp2[j] = 1 + Math.min(dp1[j], dp2[j - 1]);
                }
            }

            int[] tmp = dp1;
            dp1 = dp2;
            dp2 = tmp;
        }

        return dp1[n - 1];
    }
}