X

LEETCODE 1246. Palindrome Removal 解题思路分析

题目大意:

删除回文子数组

给你一个整数数组 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.

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

View Comments (1)

  • Hey There. I found your blog using msn. This is a very well written article.
    I'll make sure to bookmark it and come back to
    read more of your useful info. Thanks for the post.
    I'll definitely return.