合并相邻同色方块的最小成本问题（颜色扩展与成本收益） 题目描述： 有一个由 n 个方块排成一行的序列，每个方块有一个颜色（用一个小写字母表示）。你可以进行如下操作：选择一段连续的、颜色相同的方块，将它们合并成一个新方块，新方块的颜色可以是任意颜色（不一定与原颜色相同），但合并的成本为：合并的方块数量的平方加上新颜色对应的固定成本（不同颜色可能有不同成本，用一个数组 cost[color] 给出）。目标是经过若干次合并操作后，最终只剩下一个方块，求最小总成本。 注意： 合并操作必须针对连续且颜色相同的方块段。 合并后的新方块颜色可以任意选择（即使与原来不同），但需要支付该颜色的固定成本。 每次合并的成本 = 合并的方块数量的平方 + cost[ 新颜色 ]。 示例： 方块颜色序列： "aabb" 颜色固定成本：cost[ 'a'] = 1, cost[ 'b' ] = 2 初始序列：a a b b 一种可能的合并方案： 合并前两个 'a'，选择新颜色为 'a'，成本 = 2² + 1 = 5，序列变为：a b b 合并后两个 'b'，选择新颜色为 'a'，成本 = 2² + 1 = 5，序列变为：a a 合并两个 'a'，选择新颜色为 'a'，成本 = 2² + 1 = 5，总成本 = 5+5+5=15 但可能存在更优方案，需要动态规划求解。 解题思路 这个问题是“移除盒子”类问题的扩展，但加入了颜色可变和颜色成本。难点在于：合并后新颜色可任意选，这会影响后续合并的成本。 我们采用区间动态规划，但状态需要额外记录“与右端点颜色相同的连续块长度”或“合并后左侧遗留的颜色信息”。这里我们使用一种经典思路： dp[ l][ r][ k] 表示将区间 [ l, r ] 合并，并且此时区间右侧有 k 个与方块 r 颜色相同的方块（这些方块可能是原始就同色，也可能是合并后变成同色）时，合并成一种颜色的最小成本。 但本题颜色可变，所以还要考虑最终颜色。我们可以改进为： dp[ l][ r][ c] 表示将区间 [ l, r ] 合并成一个颜色为 c 的方块的最小成本。 但这样颜色种类多时状态会很大。另一种更高效的方法： 状态定义： dp[ l][ r][ len] 表示：考虑区间 [ l, r]，并且在区间左侧已经有一个长度为 len 的连续同色块，颜色与 nums[ l] 相同，将所有这些（包括左侧这个同色块和区间 [ l, r ]）合并成一个方块的最小成本。 这种方法在“移除盒子”问题中常见。但本题颜色可以改变，所以需要知道合并后的目标颜色，因此状态还要加一维颜色。 为了控制状态数，我们改为： dp[ l][ r][ c] 表示将区间 [ l, r ] 合并成一个颜色为 c 的方块的最小总成本。 转移时，我们枚举最后一次合并操作：将区间 [ l, m] 合并成颜色 c，区间 [ m+1, r ] 合并成颜色 c，然后合并这两个颜色为 c 的块。但这样会重复计算合并成本，因为最后一次合并两个块时，块大小可能大于 1。 更精确的状态设计 我们定义 dp[ l][ r][ k] 表示：将区间 [ l, r] 的方块合并，并且在合并完成后，在区间左侧附加了 k 个颜色与 nums[ l ] 相同的虚拟方块（这些虚拟方块是之前合并得到的），将所有这些合并成一个方块的最小成本。 但这个定义在本题中不方便处理颜色变化。 我们换一种： dp[ l][ r][ c] 表示将区间 [ l, r ] 全部合并成一个颜色为 c 的方块的最小成本。 转移方程： 如果直接将整个区间一次合并成颜色 c，成本 = (r-l+1)² + cost[ c ]。 否则，我们可以在区间内找一个分界点 m，将 [ l, m] 合并成颜色 c，[ m+1, r] 合并成颜色 c，然后合并这两个颜色 c 的块。但这样合并两个颜色 c 的块时，它们的大小分别是 size1 和 size2，合并成本是 (size1+size2)² + cost[ c ]，但这会与之前的成本计算重复。 为了避免重复，我们考虑另一种分割：第一次合并时，是将一段连续相同颜色的原始块合并成颜色 c，然后与其它部分合并。 更通用的思路是： 枚举区间 [ l, r] 中所有与 nums[ l] 颜色相同的位置 p，先处理 [ l+1, p-1] 合并掉，然后 nums[ l] 和 nums[ p ] 以及它们之间可能已经合并的部分一起合并。 标准解法步骤 我们采用类似“移除盒子”的 DP 思路，但加上颜色选择的成本。 定义 dp[ l][ r][ k] 表示：区间 [ l, r] 中，在区间前面已经有 k 个方块与 nums[ l ] 颜色相同（这 k 个方块是虚拟的，表示在之前合并中得到的同色块），将所有这些（总共区间长度 + k 个方块）合并成一个方块的最小成本。 这个状态中，我们假设最终合并成的颜色与 nums[ l ] 相同（因为我们可以先不决定最终颜色，但在最后一步合并时再选择颜色）。 转移： 将开头的 k+1 个同色块（k 个虚拟 + 位置 l 的方块）与后面某个同色块一起合并。 在 [ l, r] 中找一个位置 p 使得 nums[ p] == nums[ l]，我们考虑将 [ l+1, p-1 ] 先合并掉（这部分的颜色任意），然后 l 和 p 以及虚拟的 k 个块就可以一起合并。 所以： dp[ l][ r][ k] = min{ dp[ l+1][ p-1][ 0] + dp[ p][ r][ k+1] } 对所有 p∈[ l, r] 且 nums[ p]==nums[ l ]。 另外，也可以直接将开头的 k+1 个同色块合并成一个方块（选择颜色为某一种），然后处理剩下的区间。 即：dp[ l][ r][ k] = min_ {c} { (k+1)² + cost[ c] + dp[ l+1][ r][ 0 ] } 但这样复杂度较高，因为要枚举颜色 c。 我们可以改进： 设 f[ l][ r] 表示将区间 [ l, r ] 完全合并成一个方块的最小成本（不限定颜色）。 那么 f[ l][ r] = min_ {c} { dp[ l][ r][ 0 ] 但最终颜色为 c 的成本 }。 但我们可以将 cost[ c ] 放在最后一步合并时加，即合并 x 个同色方块时成本 = x² + minCost，其中 minCost 是所有颜色固定成本的最小值（因为最终颜色可选）。 但注意：如果某次合并不选最终颜色，可以选一个成本低的颜色，但后续再合并时可能改变颜色。 简化版最优状态设计 经过思考，最清晰的方法是： dp[ l][ r][ c] 表示将 [ l, r ] 合并成一个颜色为 c 的方块的最小成本。 转移： 一次合并整个区间：dp[ l][ r][ c] = (r-l+1)² + cost[ c ]。 枚举分界点 m (l ≤ m < r)： dp[ l][ r][ c] = min{ dp[ l][ m][ c] + dp[ m+1][ r][ c] - (size1)² - cost[ c ]? } 这样会有重复减去成本的问题，所以不适用。 实际上，正确的合并方式： dp[ l][ r][ c] = min{ dp[ l][ m][ c] + f[ m+1][ r] } 其中 f[ m+1][ r] 表示将 [ m+1, r] 合并成一个方块的最小成本（颜色任意），然后合并这两个块时，左边颜色已经是 c，右边颜色任意，合并这两个块的成本是 (size_ left + size_ right)² + cost[ c ] 吗？不对，因为右边颜色可能不是 c，需要先将其变为 c 再合并，或者直接合并时选择颜色 c，这样右边的块要先变成 c，成本已包含在 f 中。 这样很乱。 更简洁的解法（区间 DP + 预处理） 我们注意到，合并 x 个同色方块的成本是 x² + cost[ 颜色 ]。 如果我们知道最终颜色，那么在整个过程中，我们可以将所有方块最终变成这个颜色，但合并时如果两段颜色不同，需要额外成本将它们先变成同色。 实际上，我们可以逆向思考：最终所有方块会变成一种颜色，我们枚举这种颜色 C。 对于固定的最终颜色 C，问题变成：每次可以合并一段连续同色方块（原始或合并后），合并后颜色必须变成 C，成本是长度平方 + cost[ C ]。但这样每次合并后颜色都是 C，那后续合并时，如果相邻块颜色都是 C，就可以合并。 这等价于：初始方块有不同颜色，每次可以选择一段连续同色方块合并，合并后颜色可以是任意颜色，但最终必须全部是 C，求最小成本。 我们可以在 DP 时记录最终颜色。 定义 f[ l][ r] 表示将 [ l, r ] 合并成一个方块，且这个方块颜色可以是任意颜色时的最小成本。 转移时，考虑将 [ l, r ] 分成若干段，每段分别合并成一个颜色，然后这些段再合并。但这样就是区间 DP 标准形式： f[ l][ r] = min{ f[ l][ m] + f[ m+1][ r] } 对于 l ≤ m < r。 但这样没考虑合并同色段的收益。 最终采用的方法（类似石子合并但带颜色） 我们定义 dp[ l][ r] 表示将 [ l, r ] 完全合并成一个方块的最小成本。 合并时，最后一次操作一定是将某连续几段颜色相同的块合并成一个块。 所以我们枚举最后一个同色段：假设在 [ l, r ] 中，位置 p1, p2, …, pk 颜色相同，我们最后将这些同色位置连同它们之间已合并的部分一起合并。 具体地，设 color[ l] = cl，我们在 [ l, r] 中找另一个位置 p 使得 color[ p ] = cl，然后考虑： 先将 [ l+1, p-1] 合并掉（成本 dp[ l+1][ p-1 ]），然后 l 和 p 连同它们之间已合并的部分（其实已合并成一个块）以及左边可能有的同色虚拟块一起合并。 但这样需要额外状态记录左边同色块数。 所以我们回到“移除盒子”模型： 定义 dp[ l][ r][ k] 表示：在区间 [ l, r] 中，l 左边有 k 个与 color[ l ] 同色的方块（这些方块会与 l 一起合并），将所有这些（区间+左边k个）合并成一个方块的最小成本。 转移： 直接将左边 k+1 个同色块合并：dp[ l][ r][ k] = (k+1)² + minCost + dp[ l+1][ r][ 0 ]，其中 minCost 是 cost 数组的最小值（因为可以选择任意颜色，选成本最小的颜色）。 或者，在区间中找一个位置 p 使得 color[ p] = color[ l]，先将 [ l+1, p-1 ] 合并掉，然后 l 和 p 以及左边 k 个块一起合并： dp[ l][ r][ k] = min{ dp[ l+1][ p-1][ 0] + dp[ p][ r][ k+1 ] }。 最终答案 = dp[ 0][ n-1][ 0 ]。 这个状态转移中，我们隐含了最后合并时选择颜色为 cost 最小的颜色，因为 (k+1)² + minCost 是合并 k+1 个同色块的最小成本。 算法步骤 预处理 minCost = min(cost[ 所有颜色 ])。 初始化 dp[ l][ r][ k] 为无穷大，dp[ l][ l-1][ k ] 不存在。 按区间长度从小到大计算： 对每个区间 [ l, r ]，对每个 k 从 0 到 n： a. 选择1：直接合并左边 k+1 个同色块（包括 l）变成一种颜色（选最小成本颜色），然后合并剩余区间 [ l+1, r ]： cost1 = (k+1)² + minCost + dp[ l+1][ r][ 0 ] （如果 l+1 > r 则后面为 0）。 b. 选择2：在区间中找 p 满足 l < p ≤ r 且 color[ p] = color[ l]，先合并 [ l+1, p-1 ]，然后 l 和 p 以及左边 k 个块一起处理： cost2 = dp[ l+1][ p-1][ 0] + dp[ p][ r][ k+1 ]。 dp[ l][ r][ k ] = min(cost1, cost2 的 min)。 最终 dp[ 0][ n-1][ 0 ] 就是答案。 示例计算 颜色序列 "aabb"，cost[ 'a']=1, cost[ 'b' ]=2。 minCost = 1。 区间 [ 0,0 ]： dp[ 0][ 0][ k ] = (k+1)² + 1。 区间 [ 1,1 ]：类似。 区间 [ 0,1 ]（aa）： dp[ 0][ 1][ 0 ] = min( 直接合并：1²+1+dp[ 1][ 1][ 0 ] = 1+1+((1)²+1)=1+1+2=4， 或 p=1 同色：dp[ 1][ 0][ 0]+dp[ 1][ 1][ 1]，dp[ 1][ 0][ 0]=0，dp[ 1][ 1][ 1 ]=(2)²+1=4+1=5，总=5。 ) 取 4。 类似可算得整个序列，最终得到最小成本。 复杂度 状态数 O(n³)（l, r, k），每个状态转移需要枚举 p，总复杂度 O(n⁴)，n ≤ 100 时可用优化（预处理同色位置）降至 O(n³)。 这样我们就得到了这个问题的完整区间 DP 解法。