関小君刷题记

题目大意：

删除回文子数组

给你一个整数数组 arr，每一次操作你都可以选择并删除它的一个 回文 子数组 arr[i], arr[i+1], …, arr[j]，其中 i <= j。

注意，每当你删除掉一个子数组，右侧元素都会自行向前移动填补空位。

请你计算并返回从数组中删除所有数字所需的最少操作次数。

示例 1：

输入：arr = [1,2]
输出：2

示例 2：

输入：arr = [1,3,4,1,5]
输出：3
解释：先删除 [4]，然后删除 [1,3,1]，最后再删除 [5]。

提示：

• 1 <= arr.length <= 100
• 1 <= arr[i] <= 20

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1246

解题思路分析：

这是一道动态规划的题目，难度级别为Hard。我在之前的文章说过，所有动态规划（DP）题目都可以转化为递归加记忆数组来实现，本人更青睐于递归，因此本题仍然使用递归来解题。

我们先定义一个递归方法help，help(from, to)的返回值代表，删除区间[from, to]内所有数字所需要的次数。我们从from+1开始循环到to，用每一个数i与from作比较，如果两数(当前数i和from)相同，分两种情况考虑，若当前数i与from相邻，说明这两个数可以组成回文，因此，可以使用一次操作删掉这两个数字，即：

公式1：help(from, to) = 1 + help(i+1, to)。

若当前数i与from不相邻，那么当前数与from是可以融合到区间[from+1, i-1]之内，也就是说， help(from, i) == help(from+1, to-1)。这里解释一下原因，举个例子，比如区间[from, i]为：

[1,2,3,1] // 等于[2,3]

将1，2，3，1全部删除需要2步：

1. 删除2，变为1，3，1
2. 此时1，3，1为回文，可一次删除

也就是说，除去区间首尾相同的元素之外，中间部分经过一系列删除之后，一定能剩下1个单独的数字或者一个单独的回文，不论是哪种情况，中间最后剩余的部分都能与区间首尾共同组成一个回文，因此首尾部分可以与中间剩余部分一次性删除掉。结论： 如果两数(当前数i和from)相同，并且当前数i与from不相邻时，

公式2： help(from, to) = help(from+1, i-1) + help(i+1, to)

当循环完区间内所有元素（从from+1循环到to）之后，我们还有另一种选择，即将首元素单独删除，剩下的部分交给递归子问题去解决。即：

公式3： help(from, to) = 1 + help(from+1, to)

有了上述3个公式，本题即可完美解决。另外别忘记添加记忆数组，以防止重复计算（相当于动态规划使用到的dp数组）。我们定义一个二维数组memo[][]，memo[i][j]代表区间[i，j]。

实现代码：

int[][] memo; // 记忆数组
public int minimumMoves(int[] arr) {
    // 初始化记忆数组
    memo = new int[arr.length][arr.length];
    return help(arr, 0, arr.length - 1);
}

int help(int[] arr, int from, int to) {
    // 区间范围不合理，返回0
    if (to < from) return 0;
    // 区间长度为1，返回1
    if (to == from) return 1;
    // 如果该区间曾经计算过，返回之前的计算结果
    if (memo[from][to] != 0) return memo[from][to];
    // 返回值
    int res = Integer.MAX_VALUE;
    // 区间首元素的值
    int fromValue=arr[from];
    // 从区间第二个元素循环到区间尾部
    for (int i = from + 1; i <= to; i++) {
        // 如果当前元素等于区间首元素
        if (fromValue == arr[i]) {
            int result = 0;
            if(i-from==1){ // 当前元素与首元素相邻
                result = 1 + help(arr, i + 1, to);
            }else{ // 当前元素与首元素不相邻
                result = help(arr, from + 1, i - 1)
                       + help(arr, i + 1, to);
            }
            // 将最小值更新到返回结果
            res = Math.min(res, result);
        }
    }
    // 我们还可以选择将首字母单独删去后的情况
    res = Math.min(res, 1 + help(arr, from + 1, to));
    // 将本区间的计算结果保存至记忆数组，防止今后重复计算
    memo[from][to] = res;
    return res;
}

本题解法执行时间为18ms。

Runtime: 18 ms, faster than 90.27% of Java online submissions for Palindrome Removal.

Memory Usage: 36.6 MB, less than 100.00% of Java online submissions for Palindrome Removal.

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1246-palindrome-removal-解题思路分析/