合并相邻同色方块的最小成本问题（带消除规则与成本收益）
题目描述
给定一个长度为 n 的数组 colors，表示一排方块的颜色（用整数表示）。你可以执行以下操作：
- 选择两个相邻且颜色相同的方块，将它们合并成一个方块，新方块的颜色不变，但合并操作需要花费成本
costMerge。 - 合并后，如果新方块与相邻的任意一侧方块颜色相同，则会自动触发消除：相同颜色的连续一整段会立即消失，并产生收益
gainElim（收益为负值表示额外成本）。消除后，剩余部分会靠拢。
你的目标是经过一系列操作，使得所有方块最终合并成一个方块，并使得总成本（合并成本减去消除收益）最小。求最小总成本。
例如：colors = [1, 1, 2, 2, 1]，costMerge = 3，gainElim = 5。
一种方案：
- 合并位置 0 和 1 的
1，成本 3 →[1, 2, 2, 1]。 - 合并位置 1 和 2 的
2，成本 3 →[1, 2, 1]，此时中间2两侧颜色不同，不触发消除。 - 合并位置 0 和 1 的
1和2？不行，颜色不同不可合并。 - 合并位置 1 和 2 的
2和1？不行。 - 实际上需要先合并两个
2触发消除：合并位置 1 和 2 的2，成本 3 →[1, 2, 1]，但此时2两侧为1和1吗？不，数组是[1, 2, 1]，2在中间，两侧是1和1，但不相邻，因为中间是2自己。 - 正确操作：先合并两个
2（原位置 2 和 3）：合并后数组为[1, 2, 1]，然后2两侧颜色相同（都是1），触发消除，2消失，收益 5 → 数组变为[1, 1]。 - 合并两个
1，成本 3 →[1]，结束。
总成本 = 3 + 3 - 5 + 3 = 4。
解题思路
这是一个区间动态规划问题，因为每次操作影响一个连续区间，且最终要合并整个区间。难点在于消除规则可能导致区间分裂。
定义状态
dp[l][r][k] 表示将区间 [l, r] 内的方块，处理成 左侧有连续 k 个与 colors[l] 颜色相同的方块 的最小成本。这里 k 表示区间 [l, r] 经过内部合并消除后，剩下的一段颜色为 colors[l] 的方块个数（0 ≤ k ≤ r-l+1）。
为什么需要 k？因为消除规则可能让区间内部分方块消失，剩余的与左端同色的方块可能与区间外的方块合并。
状态转移
考虑区间 [l, r]：
- 如果
k = 0，表示区间被完全消除，不剩下任何方块。这需要区间内所有方块通过合并和消除全部清空，成本为 0（但必须可达）。 - 如果
k > 0，则第一个方块（位置l）必须保留，且颜色为colors[l]。我们考虑如何从小区间转移。
关键思想：枚举区间内第一个与 colors[l] 相同颜色的位置 m（l < m ≤ r 且 colors[m] == colors[l]），将区间分成三部分：
[l+1, m-1]：这部分要在内部完全消除（变成空），成本为dp[l+1][m-1][0]。[m, r]：这部分处理成左侧有k-1个与colors[l]同色的方块（因为m与l同色，合并后相当于增加一个同色块）。
但这样会漏掉合并两个同色块的成本与消除收益。更准确的做法是：
将 [l, r] 视为：先让 [l+1, m-1] 完全消除，然后 colors[l] 和 colors[m] 可以“连接”在一起（因为它们中间已空），此时触发一次合并（成本 costMerge），并可能触发消除。消除规则是：如果合并后，同色块的连续长度达到某个值，且两侧颜色相同，则消除中间段。但这里我们已经在 dp 状态中隐式处理了消除：k 表示最终剩下的同色块数，如果 k=0 表示全消除，收益为 gainElim 乘以消除的块数？
更精确的转移方程
我们重新定义状态：dp[l][r] 表示将区间 [l, r] 完全消除的最小成本（即区间变为空）。但这样无法处理最后剩下方块的情况，因为最后整个数组要剩下一个方块。因此我们增加一维表示剩下多少个同色块，如之前所述。
但为了简化，可以这样设计：
dp[l][r][k] 表示区间 [l, r] 经过操作后，剩下 k 个颜色为 colors[l] 的连续方块的最小成本（k >= 1）。
转移时，枚举 m（l < m ≤ r, colors[m] == colors[l]）：
- 将
[l+1, m-1]完全消除，成本为f[l+1][m-1]（其中f[i][j]是区间完全消除的最小成本，可从dp推出）。 - 然后
l和m现在相邻，合并它们，成本costMerge。 - 合并后，如果
[l, m]这一段同色块与更左侧或右侧同色，可能触发消除，但这里我们只考虑区间内部，所以假设不会与外部触发。 - 之后，
[m, r]区间要处理成k-1个同色块，成本为dp[m][r][k-1]。
那么：
dp[l][r][k] = min over m (f[l+1][m-1] + costMerge + dp[m][r][k-1])
其中 f[l][r] 表示区间 [l, r] 完全消除的最小成本。
如何求 f[l][r]？
完全消除区间，可以枚举最后一个消除的同色块组。假设区间 [l, r] 最后消除的是颜色为 colors[l] 的一段，其长度为 k，那么：
f[l][r] = min over k (dp[l][r][k] + gainElim * k)
因为消除长度为 k 的同色块组，获得收益 gainElim * k（收益为负则是成本）。
边界条件
- 单个区间
dp[i][i][1] = 0（不需要合并，已有一个块）。 - 完全消除单个区间
f[i][i] = gainElim * 1（直接消除这个块，收益gainElim）。
计算顺序
区间长度从小到大计算。先算 dp[l][r][k]，再算 f[l][r]。
最终整个数组 [0, n-1] 要剩下 1 个块，所以答案是 dp[0][n-1][1]。
示例计算
以例子 [1,1,2,2,1]，costMerge=3，gainElim=5 为例：
- 区间长度 1：
dp[i][i][1]=0，f[i][i]=5。 - 区间长度 2：
[0,1]颜色相同，dp[0][1][2] = 0+3+?实际上 m 只能等于 1，f[1][0]空区间成本 0，dp[1][1][1] = 0，所以dp[0][1][2] = 0+3+0 = 3。f[0][1] = dp[0][1][2] + 5*2 = 3 + 10 = 13，但也可以直接合并两个 1 再消除，成本 3-5*2? 注意收益是消除时得到，所以总成本 3-10 = -7？这里需要明确收益是正值还是负值。题目说“收益 gainElim”，收益为 5 表示得到 5，所以成本减 5。我们方程中f[l][r] = dp[l][r][k] + gainElim * k，如果 gainElim=5，f[0][1] = 3 + 5*2 = 13，这是正成本，不合理。实际上应该用dp[l][r][k] - gainElim*k才表示消除的收益减少了成本。
修正：消除收益是减少成本，所以f[l][r] = min_k (dp[l][r][k] - gainElim * k)。
这样f[0][1] = 3 - 10 = -7。
- 继续计算可得到最终结果。
最终方程修正
dp[l][r][k]转移不变。f[l][r] = min_{k} (dp[l][r][k] - gainElim * k)。- 最终答案：整个区间剩下 1 个块，总成本 =
dp[0][n-1][1]。
复杂度
状态数 O(n³)，每个状态转移 O(n)，总 O(n⁴)，可用优化减少。
小结
本题的核心在于状态设计：除了区间端点，还要记录剩下多少个同色块，以处理合并后的消除收益。通过分治思想，将区间分解为子区间，逐步计算合并与消除的最小成本。