Leetcode 1246:删除回文子数组(超详细的解法!!!)
in leetcode with 0 comment

Leetcode 1246:删除回文子数组(超详细的解法!!!)

in leetcode with 0 comment

给你一个整数数组 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)首先可以将它单独处理 2)可以找到和它相同的元素,如果此时两者之间是回文串的话,那么我们可以将这两个元素加上去。最后代码非常简洁:

from functools import lru_cache
class Solution:
    def minimumMoves(self, arr: List[int]) -> int:
        @lru_cache(None)
        def dfs(l, r):
            if l > r:
                return 0
            res = 1 + dfs(l + 1, r)
            for i in range(l + 1, r + 1):
                if arr[i] == arr[l]:
                    res = min(res, dfs(l + 1, i - 1) + dfs(i + 1, r) + (l + 1 == i)) 
            return res
        return dfs(0, len(arr) - 1)

需要注意的上面l + 1 == i的写法,实际上是考虑了第二种情况中间为空的情况。

同样dfs加记忆化可以解的问题也可以通过动态规划来做,我们定义函数$f(i,j)$表示区间[i,j]的最少删除次数,那么

其中k表示中间字符串位置,范围在区间[i,j]中。

class Solution:
    def minimumMoves(self, arr: List[int]) -> int:
        n = len(arr)
        mem = [[0] * (n + 1) for _ in range(n + 1)]
        for l in range(1, n + 1):
            i, j = 0, l - 1
            while j < n:
                if l == 1:
                    mem[i][j] = 1
                else:
                    mem[i][j] = 1 + mem[i + 1][j]
                    for k in range(i + 1, j + 1):
                        if arr[k] == arr[i]:
                            mem[i][j] = min(mem[i][j], mem[i + 1][k - 1] + mem[k + 1][j] + (i + 1 == k))
                i += 1
                j += 1
        return mem[0][n - 1]

我将该问题的其他语言版本添加到了我的GitHub Leetcode

如有问题,希望大家指出!!!

「如果我的文章对你有很大帮助,那么不妨~!」

coordinate

谢谢老板O(∩_∩)O~

使用微信扫描二维码完成支付

Responses