区间动态规划例题：删除回文子数组的最小操作次数 题目描述 给你一个整数数组 arr ，你可以执行若干次操作，每次操作从数组中删除一个 回文子数组 （即数组中的一个连续子序列，并且这个子序列从前往后读和从后往前读是一样的）。一次操作中，删除一个长度为 k 的回文子数组的代价为 1（即一次操作计数为 1）。 你的目标是删除整个数组，问最少需要多少次操作。 示例 1 输入： arr = [1, 2, 3] 输出：3 解释：每个元素自己就是一个长度为 1 的回文子数组，所以需要 3 次操作分别删除它们。 示例 2 输入： arr = [1, 2, 1] 输出：1 解释：整个数组 [1, 2, 1] 本身就是一个回文数组，所以一次操作就可以全部删除。 示例 3 输入： arr = [1, 3, 4, 1, 5] 输出：3 解释：一种方案是： 删除 [4] （一次操作，剩下 [1, 3, 1, 5] ） 删除 [1, 3, 1] （一次操作，剩下 [5] ） 删除 [5] （一次操作，完成） 解题过程 1. 问题分析与定义状态 这是一个数组删除问题，每次只能删除一个 连续的回文子数组 ，目标是全部删完的最少操作次数。 数组长度为 n，我们考虑用 区间动态规划 解决。 定义 dp[i][j] 表示删除子数组 arr[i...j] （闭区间）所需的最少操作次数。 最终答案就是 dp[0][n-1] 。 2. 状态转移的思路 我们考虑子数组 arr[i...j] 如何被删除： 情况1 ：如果 arr[i] == arr[j] ，并且 dp[i+1][j-1] 已知，那么我们可以考虑 将 arr[ i] 和 arr[ j] 与中间部分一起删除 ，但具体如何删除需要分情况： 如果 arr[i] 和 arr[j] 在中间部分被删除的某次操作中，与中间部分一起构成一个回文，那么 dp[i][j] 可能等于 dp[i+1][j-1] （即中间部分删除后，两端的数自动随着中间的回文子数组一起被删除）。 但要注意：如果中间部分 arr[i+1...j-1] 被删除后， arr[i] 和 arr[j] 并不一定能在一次操作中与中间合并，因为回文要求整个区间是回文。 所以更保险的做法是： 将问题分解为删除更小的区间 。 情况2 ：我们可以将区间 [i, j] 分成两个部分： [i, k] 和 [k+1, j] ，分别删除，总操作数为两者之和。 即： dp[i][j] = min(dp[i][k] + dp[k+1][j]) ，其中 k 从 i 到 j-1 。 情况3 ：如果 arr[i] == arr[j] ，我们可以考虑一种特殊的合并方式： 当我们删除中间部分 arr[i+1...j-1] 后，剩下的 arr[i] 和 arr[j] 可以 在一次操作中合并删除 （因为 arr[i]==arr[j] ，且中间部分已删除， arr[i] 和 arr[j] 相邻，构成回文子数组 [arr[i], arr[j]] ）。 但要注意：如果中间部分删除的最后一次操作留下的边界与 arr[i] 或 arr[j] 相同，它们可能在更早的时候就被一起删除了，所以我们不能简单认为 dp[i][j] = dp[i+1][j-1] 。 实际上，更一般的处理是： 如果 arr[ i] == arr[ k]（i < k ≤ j） ，那么我们可以将区间 [i, j] 分成三部分： 先删除 [i+1, k-1] 再删除 [k, j] （其中 arr[i] 和 arr[k] 在同一个回文子数组中） 但这样会多算。更好的方法是： 当 arr[ i] == arr[ k] 时，我们可以认为删除 [ i, j] 可以先将 [ i+1, k-1] 删除，然后 arr[ i] 和 arr[ k] 可以与 [ k, j] 的剩余部分一起删除 。 这推导出一个状态转移： dp[i][j] = min(dp[i][j], dp[i+1][k-1] + dp[k][j]) ，当 arr[i] == arr[k] 且 k 在 i 到 j 之间。 注意：当 k = i 时， dp[i+1][k-1] 无意义，我们单独处理。 特殊情况 ：如果整个区间 [i, j] 本身是回文，那么 dp[i][j] = 1 。 3. 正式状态转移方程 我们按区间长度从小到大计算。 初始化：单个元素的区间一定是回文，所以 dp[i][i] = 1 。 对长度 len = 2 到 n 的每个区间 [i, j] ： 先假设最坏情况：每个元素单独删除，即 dp[i][j] = len 。 如果 arr[i] == arr[j] ： 如果 len == 2 ，则 dp[i][j] = 1 （两个相同元素构成回文）。 否则， dp[i][j] = min(dp[i][j], dp[i+1][j-1]) 。 这是因为我们可以将两端与中间部分一起删除，而中间部分删除后，两端自然相邻构成回文，所以总操作数等于中间部分的操作数。 枚举分割点 k 从 i 到 j-1 ： dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j]) 。 枚举中间与 arr[i] 相等的元素位置 k （ i < k ≤ j 且 arr[i] == arr[k] ）： 考虑将区间分成 [i+1, k-1] 和 [k, j] 两部分，但注意：删除 [i+1, k-1] 后， arr[i] 和 arr[k] 相邻，可以在删除 [k, j] 时一起被删。 所以转移为： dp[i][j] = min(dp[i][j], dp[i+1][k-1] + dp[k][j]) 。 这里当 k = i+1 时， dp[i+1][k-1] 表示空区间，我们定义空区间操作数为 0。 当 k = i 时，这个情况已由 arr[i] == arr[j] 和 dp[i+1][j-1] 覆盖。 最终 dp[0][n-1] 即为答案。 4. 边界与初始化细节 空区间操作数为 0，在代码中注意处理下标。 当 len=2 且两数相等时，直接为 1。 当 len=2 且两数不等时，为 2。 5. 示例推导（arr = [ 1, 3, 4, 1, 5 ]） n=5，下标 0~4。 初始化单个元素： dp[i][i]=1 。 长度 2： [ 0,1 ]: 1≠3 → dp=2 [ 1,2 ]: 3≠4 → dp=2 [ 2,3 ]: 4≠1 → dp=2 [ 3,4 ]: 1≠5 → dp=2 长度 3： [ 0,2 ]: arr0=1, arr2=4 不等，先分割： dp[ 0][ 0]+dp[ 1][ 2 ]=1+2=3 dp[ 0][ 1]+dp[ 2][ 2 ]=2+1=3 最小为 3。 [ 1,3 ]: arr1=3, arr3=1 不等，分割： dp[ 1][ 1]+dp[ 2][ 3 ]=1+2=3 dp[ 1][ 2]+dp[ 3][ 3 ]=2+1=3 最小为 3。 [ 2,4 ]: arr2=4, arr4=5 不等，分割： dp[ 2][ 2]+dp[ 3][ 4 ]=1+2=3 dp[ 2][ 3]+dp[ 4][ 4 ]=2+1=3 最小为 3。 长度 4： [ 0,3]: arr0=1, arr3=1 相等，先考虑 dp[ 1][ 2 ]=2，所以可能为 2。 再分割： k=1: arr0≠arr1 k=2: arr0≠arr2 k=3: arr0=arr3，此时 dp[ 1][ 2]+dp[ 3][ 3 ]=2+1=3 取最小为 2。 [ 1,4 ]: arr1=3, arr4=5 不等，分割取最小： dp[ 1][ 1]+dp[ 2][ 4 ]=1+3=4 dp[ 1][ 2]+dp[ 3][ 4 ]=2+2=4 dp[ 1][ 3]+dp[ 4][ 4 ]=3+1=4 最小为 4。 长度 5：[ 0,4 ]: arr0=1, arr4=5 不等，先分割： dp[ 0][ 0]+dp[ 1][ 4 ]=1+4=5 dp[ 0][ 1]+dp[ 2][ 4 ]=2+3=5 dp[ 0][ 2]+dp[ 3][ 4 ]=3+2=5 dp[ 0][ 3]+dp[ 4][ 4 ]=2+1=3 → 最小为 3 检查 arr0 与后面相等的元素：arr3=1，k=3： dp[ 1][ 2]+dp[ 3][ 4 ] = 2+2=4，不比 3 小。 所以最终 dp[ 0][ 4 ]=3。 结果与示例一致。 总结 本题是区间 DP 的经典变形，关键点在于： 当区间两端相等时，可能通过删除中间部分来减少操作数。 需要枚举分割点，将大区间拆成两个小区间分别删除。 注意特殊情况：整个区间本身是回文，则操作数为 1。 时间复杂度 O(n³)，空间复杂度 O(n²)。