合并区间以形成目标数组的最小合并次数

题目描述

给你一个整数数组 target，它是你最终想要获得的数组。你初始有一个与 target 长度相同的数组 initial，其中所有元素都是 0。每次操作，你可以选择 initial 中任意一段连续的子数组，并将该子数组内的所有元素替换为同一个任意正整数。你的目标是经过若干次操作后，使 initial 变成与 target 完全相同的数组。求所需的最少操作次数。

示例：
输入：target = [3, 3, 1, 3]
输出：2
解释：
初始： [0, 0, 0, 0]
第一步：将子数组 [0, 1]（前两个元素）替换为 3 → [3, 3, 0, 0]
第二步：将子数组 [2, 3]（后两个元素）替换为对应的目标值 [1, 3] → [3, 3, 1, 3]

解题过程

我们先明确几个要点：

• 每次操作可以将任意长度的连续子数组全部设置为同一个值，这个值可以是任意正整数，不一定是最终的目标值，但最后必须与 target 完全一致。
• 初始数组全部是 0，目标数组是 target。
• 我们要找到最少的操作次数。

第一步：问题转化

这道题可以看作一个“区间覆盖”问题。每次操作覆盖一个区间，将其设为一个值。最终要让整个数组与 target 匹配。
关键在于，如果 target 中某个位置的值和它相邻位置的值相同，那么在一次操作中，它们可以被一起覆盖成这个值，从而可能减少操作次数。

但注意：即使相邻位置值相同，也可能需要分开操作，因为可能受到其他位置的值的干扰。例如，target = [1, 2, 1]，虽然第一个和第三个都是 1，但中间是 2，如果一次覆盖成 1 就破坏了中间的值，所以必须分开覆盖。

因此，这个问题可以转化为：

将 target 数组划分成若干段，使得每一段内部的值相同，然后每一段可以用一次操作完成覆盖。
但是，如果相邻两段的值相同，它们是否可以在同一次操作中被覆盖？
不一定，因为如果它们之间有别的值隔开，那么一次覆盖就会把中间的值也覆盖掉，从而需要额外操作来修正中间的值，可能得不偿失。

所以我们需要一个更精细的方法。

第二步：区间动态规划思路

定义 dp[i][j] 表示将区间 [i, j] 变成与 target 对应区间一致所需的最少操作次数。
最终答案是 dp[0][n-1]，其中 n 是数组长度。

区间 DP 的常见思路：

• 如果区间长度为 1，即 i == j，那么初始是 0，目标值是 target[i]，一次操作（覆盖这一个位置）就可以完成。所以 dp[i][i] = 1。
• 如果区间长度大于 1，我们考虑如何从更小的区间合并得到。

第三步：状态转移

对于区间 [i, j]，我们考虑它的第一次操作覆盖的是哪个子区间。
假设第一次操作覆盖了区间 [k, l]（其中 i ≤ k ≤ l ≤ j），并将这个区间设置为某个值 v。
这个值 v 必须等于 target 在 [k, l] 中的同一个值，因为最终这个区间内所有值都要等于 v，而且 target 中这个区间内所有值必须相同，否则不可能通过一次操作完成。

所以第一次操作覆盖的区间 [k, l] 必须满足：target[k] = target[k+1] = ... = target[l]，即这个区间在目标数组中值都相同。

然后，在覆盖了 [k, l] 之后，我们需要处理剩下的部分：

• 区间 [i, k-1] 和 [l+1, j] 还需要另外的操作来变成目标值。
• 注意，[i, k-1] 和 [l+1, j] 是独立的两段，它们之间被 [k, l] 隔开了，所以它们的操作互不影响。

那么，总操作次数是：

1（覆盖 [k, l] 这一次） + dp[i][k-1] + dp[l+1][j]（如果区间存在）。

但这样枚举 k, l 复杂度较高，我们可以优化。

第四步：优化状态转移

观察发现，我们可以从区间两端入手。

• 如果 target[i] == target[j]，那么有可能一次操作覆盖整个 [i, j] 区间为目标值 target[i]，但前提是整个区间在目标数组中值都相同。如果不是，就不行。
• 实际上，我们可以先考虑将区间两端先匹配起来，而不一定要一次性覆盖整个区间。

常见优化策略是：
如果 target[i] == target[j]，那么当我们处理完 [i+1, j-1] 后，可以在某次覆盖中把 i 和 j 一起带上，可能减少一次操作。
但必须小心，比如 [i, j] 可能被一次操作覆盖成 target[i]，然后再处理内部。

实际上，我们可以把问题看作是“合并相邻且值相同的区间可以减少操作次数”。
更准确的思路是：

定义 dp[i][j] 为最少操作次数。
如果 target[i] == target[j]，那么 dp[i][j] 可以取 dp[i+1][j] 或者 dp[i][j-1]，因为我们可以将 i 合并到右边区间的同色段，或者将 j 合并到左边区间的同色段，而不增加操作数。
但要注意，这并不总是成立，因为如果区间内颜色不同，合并可能会导致额外操作。

更安全的通用转移方程：

dp[i][j] = min(
    dp[i][k] + dp[k+1][j]  (i ≤ k < j)
)

但这样是标准的区间合并，复杂度 O(n³)。

不过，我们观察到，如果 target[i] == target[k] 且 k 是某个分界点，可能能优化。
实际上有一个经典技巧：

如果 target[i] == target[j]，那么 dp[i][j] = dp[i+1][j]，因为我们可以把 i 这个位置留到最后一次覆盖时，和 j 一起覆盖，而不增加操作数。
但要注意，这要求区间 [i, j] 中 target[i] 这个值出现的次数和位置满足一定条件，否则不一定成立。

在标准题解中，常用的优化方法是：

• 预处理每个区间是否全部相同值，如果是，则 dp[i][j] = 1。
• 否则，如果 target[i] == target[j]，可以取 dp[i+1][j] 或 dp[i][j-1]，因为 i 可以和 j 在同一次操作中完成。
• 但更准确的是，如果 target[i] == target[j]，则 dp[i][j] = dp[i][j-1]，因为我们可以把 j 合并到左边的同色段。

让我们仔细推敲：

正确状态转移（已验证的经典解法）：

1. 基础情况：dp[i][i] = 1。

2. 对于区间 [i, j]，考虑将区间分成两段 [i, k] 和 [k+1, j]，然后分别处理，最后合并结果，即 dp[i][j] = min(dp[i][k] + dp[k+1][j]) 对所有 k。

3. 如果 target[i] == target[j]，我们有一种更优的可能：先处理 [i+1, j-1]，然后将 i 和 j 一起覆盖，这样总操作数等于 dp[i+1][j-1]。但注意，如果 j = i+1 且值相同，那么 dp[i][j] = 1。
   更一般地，如果 target[i] == target[j]，那么我们可以将 i 和 j 视为同一段，在覆盖它们时一起处理，所以 dp[i][j] = dp[i+1][j] 或 dp[i][j-1]，因为覆盖 i 的时候可以顺便覆盖 j 而不增加次数。
   具体是：dp[i][j] = min(dp[i+1][j], dp[i][j-1]) 当 target[i] == target[j]。
   为什么？因为从 [i+1, j] 变成目标，然后我们把 i 用同一次操作覆盖成同样的值（与 j 相同），就完成了 [i, j]。

   但要注意，这要求 target[i] 在整个区间中的覆盖是可行的。实际上，这个递推是正确的，原因如下：
   设我们已经用最少次数将 [i+1, j] 变成了目标，那么 i 现在是 0，要变成 target[i]，由于 target[i] == target[j]，而 j 已经是目标值，我们可以在某一次覆盖中，扩大覆盖区间，把 i 也包含进去，而不增加操作次数。所以总次数等于 dp[i+1][j]。

   类似地，从 [i, j-1] 出发，也可以得到 dp[i][j] = dp[i][j-1]。

   所以最终转移方程为：

   dp[i][j] = min(dp[i+1][j], dp[i][j-1])   if target[i] == target[j]
   dp[i][j] = min(dp[i][k] + dp[k+1][j]) for k in [i, j-1]  otherwise
   

第五步：示例推导

例：target = [3, 3, 1, 3]，n=4。

• 初始化：dp[i][i] = 1。
• 区间 [0,1]：target[0]==target[1]==3，所以 dp[0][1] = min(dp[1][1], dp[0][0]) = min(1,1) = 1。
• 区间 [1,2]：值不同 (3,1)，所以 dp[1][2] = min(dp[1][1]+dp[2][2]) = 1+1=2。
• 区间 [2,3]：值不同 (1,3)，所以 dp[2][3] = 2。
• 区间 [0,2]：target[0]=3, target[2]=1 不同，枚举 k：
  k=0: dp[0][0]+dp[1][2] = 1+2=3
  k=1: dp[0][1]+dp[2][2] = 1+1=2
  取 min=2。
• 区间 [1,3]：target[1]=3, target[3]=3 相同，所以 dp[1][3] = min(dp[2][3], dp[1][2]) = min(2,2) = 2。
• 区间 [0,3]：target[0]=3, target[3]=3 相同，所以 dp[0][3] = min(dp[1][3], dp[0][2]) = min(2,2) = 2。

结果 dp[0][3] = 2，与示例一致。

第六步：算法复杂度

状态数 O(n²)，每个状态转移需要 O(n) 枚举分界点（当两端值不同时），但两端值相同时直接 O(1)。
最坏情况仍是 O(n³)，但实际在实现时可以用更优的决策优化，不过 O(n³) 在 n ≤ 200 时足够。

第七步：代码框架

def minOperations(target):
    n = len(target)
    dp = [[0] * n for _ in range(n)]
    for i in range(n):
        dp[i][i] = 1
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            if target[i] == target[j]:
                dp[i][j] = min(dp[i+1][j], dp[i][j-1])
            else:
                dp[i][j] = min(dp[i][k] + dp[k+1][j] for k in range(i, j))
    return dp[0][n-1]

总结

这个问题的核心是区间动态规划，关键点是：

1. 如果区间两端值相同，可以通过合并减少一次操作。
2. 否则，需要枚举中间的分界点，将区间分成两段处理。
3. 初始每个单元素区间需要一次操作。
4. 最终答案是整个区间的 dp 值。