---

1246. 删除回文子数组

• 标签：数组、动态规划
• 难度：困难

题目链接

• 1246. 删除回文子数组 - 力扣

题目大意

描述：给定一个整数数组 $arr$。每一步操作中，可以删除一个连续的回文子数组（子数组内元素连续，且回文指正反顺序读相同）。删除后，剩余部分会左右拼接起来。

要求：返回将整个数组删除所需的最少操作次数。

说明：

• $1 \le arr.length \le 100$。
• $1 \le arr[i] \le 20$。

示例：

• 示例 1：

输入：arr = [1,2]
输出：2
解释：不能一次性删除，因为 [1,2] 不是回文。需要先删 [1] 再删 [2]。

• 示例 2：

输入：arr = [1,3,4,1,5]
输出：3
解释：可以这样操作：删除 [4] → [1,3,1,5] → 删除 [1,3,1] → [5] → 删除 [5]。

解题思路

思路 1：区间动态规划

1. 核心思想

删除回文子数组后，剩余部分会拼接起来。这意味着一次删除可能"拉近"原本不相邻的元素，产生新的回文。比如 $[1,3,4,1,5]$ 删除中间的 $[4]$ 后，$[1,3,1]$ 变成连续的子数组，可以一次删除。

这类似于经典的"移除回文子序列"或"戳气球"类问题，可以用区间 DP 解决。定义 $dp[i][j]$ 表示删除子数组 $arr[i:j]$（从 $i$ 到 $j$，包含两端）所需的最少操作次数。

2. 阶段划分

按区间长度从小到大的顺序递推。先计算长度为 $1$ 的区间，再计算长度为 $2$ 的区间，逐渐扩展到整个数组。

3. 定义状态

$dp[i][j]$ 表示删除 $arr[i..j]$ 这个子数组所需的最少操作次数。

4. 状态转移方程

基础情况：

• $dp[i][i] = 1$（一个元素可以一次删除）。
• 如果 $arr[i] == arr[i+1]$，$dp[i][i+1] = 1$（两个相同元素构成回文，一次删除）；否则 $dp[i][i+1] = 2$。

一般情况（区间长度 $\ge 3$）：

有两种策略：

1. 分段删除：将区间分成两段分别删除，操作次数相加：

   $$dp[i][j] = \min_{k=i}^{j-1} (dp[i][k] + dp[k+1][j])$$

2. 首尾相同：如果 $arr[i] == arr[j]$，那么删除中间部分后再删首尾，可以省去一次操作：

   • 如果 $j == i+1$，$dp[i][j] = 1$（已在基础情况中处理）。
   • 否则 $dp[i][j] = \min(dp[i][j], dp[i+1][j-1])$（因为 $arr[i]$ 和 $arr[j]$ 可以"搭车"和中间的子数组一起被删除，或者等中间删除后，首尾两个相同元素构成回文一次删除）。

这个转移可能有点让人困惑，用具体的例子理解：

5. 结合示例走一遍

$arr = [1, 3, 4, 1, 5]$

计算 $dp$（只展示部分关键步骤）：

• $dp[0][0]=1, dp[1][1]=1, dp[2][2]=1, dp[3][3]=1, dp[4][4]=1$
• $dp[0][1]$：$1\ne3$ → $2$。$dp[1][2]$：$3\ne4$ → $2$。$dp[2][3]$：$4\ne1$ → $2$。$dp[3][4]$：$1\ne5$ → $2$。

区间长度 $3$：

• $dp[0][2]$：分段 $\min(dp[0][0]+dp[1][2], dp[0][1]+dp[2][2]) = \min(1+2, 2+1)=3$。$arr[0]=1 \ne arr[2]=4$ → 不进入情况 2。$dp[0][2]=3$。
• $dp[1][3]$：分段 $\min(1+2, 2+1)=3$。$arr[1]=3 \ne arr[3]=1$ → $dp[1][3]=3$。
• $dp[2][4]$：分段 $\min(1+2, 2+1)=3$。$arr[2]=4 \ne arr[4]=5$ → $dp[2][4]=3$。

区间长度 $4$：

• $dp[0][3]$：分段 $\min(dp[0][0]+dp[1][3], dp[0][1]+dp[2][3], dp[0][2]+dp[3][3]) = \min(1+3, 2+2, 3+1)=4$。$arr[0]=1 == arr[3]=1$ → $dp[0][3] = \min(4, dp[1][2]) = \min(4, 2) = 2$（先删中间 $[3,4]$ 再一起删首尾 $[1,1]$）。
• $dp[1][4]$：分段 $\min(1+3, 2+2, 3+1)=4$。$arr[1]=3 \ne arr[4]=5$ → $dp[1][4]=4$。

区间长度 $5$：

• $dp[0][4]$：分段 $\min(dp[0][0]+dp[1][4], dp[0][1]+dp[2][4], dp[0][2]+dp[3][4], dp[0][3]+dp[4][4]) = \min(1+4, 2+3, 3+2, 2+1=3)$。$arr[0]=1 \ne arr[4]=5$ → 结果为 $3$。

$dp[0][4] = 3$，对应操作：先删 $[4]$（位置 2）→ $[1,3,1,5]$ → 删 $[1,3,1]$ → $[5]$ → 删 $[5]$。

思路 1：代码

class Solution:
    def minimumMoves(self, arr: List[int]) -> int:
        n = len(arr)
        dp = [[0] * n for _ in range(n)]

        # 区间长度为 1
        for i in range(n):
            dp[i][i] = 1

        # 区间长度为 2
        for i in range(n - 1):
            dp[i][i + 1] = 1 if arr[i] == arr[i + 1] else 2

        # 区间长度 >= 3
        for length in range(3, n + 1):
            for i in range(n - length + 1):
                j = i + length - 1
                # 策略 1：分段删除
                dp[i][j] = float('inf')
                for k in range(i, j):
                    dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j])
                # 策略 2：首尾相同，可以一次消掉
                if arr[i] == arr[j]:
                    dp[i][j] = min(dp[i][j], dp[i + 1][j - 1])

        return dp[0][n - 1]

思路 1：复杂度分析

• 时间复杂度：$O(n^3)$，其中 $n$ 是数组长度。三层循环：区间长度、区间起点、分割点。$n \le 100$，$10^6$ 次操作可接受。
• 空间复杂度：$O(n^2)$，存储 $dp$ 表。