1246. 删除回文子数组

Difficulty
Hard
Tags
动态规划
URL
https://leetcode.cn/problems/palindrome-removal/
Star
给你一个整数数组 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

法 1 动态规划 - 第二类区间

思路
dp[i][j]: 删除 nums[i:j+1] 需要的最少操作数。
因为每次能删除一个回文串，所以如果 nums[i] == nums[j]则有dp[i][j] = dp[i+1][j-1]，否则需要遍历分割点k：
notion imagenotion image
题解
class Solution:
    def minimumMoves(self, arr: List[int]) -> int:
        # dp[i][j] 表示删除 arr[i:j+1] 需要多少位
        dp = [[len(arr)+10] * len(arr) for _ in arr]

        # 初始化完 一个字母 和 两个字母的 情况
        for i in range(0, len(arr)):
            dp[i][i] = 1
            if i < len(arr)-1:
                if arr[i] == arr[i+1]:
                    dp[i][i+1] = 1
                else:
                    dp[i][i+1] = 2
                

        for i in range(len(dp)-1, -1, -1):
            for j in range(i+2, len(dp[0]), 1):
                # 特殊情况， 这种一定是次数最少的
                if arr[i] == arr[j]:
                    dp[i][j] = dp[i+1][j-1]
                # 枚举割点 因为是分割为两半的，所以 k 
                else:
                    for k in range(i, j, 1):    
                        dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j])

        # print(dp)
        return dp[0][-1]