合并相邻同色方块的最小成本问题（颜色扩展版） 题目描述： 给定一个由不同颜色方块组成的序列，每个方块有一个颜色值和一个权重值。每次操作可以选择两个相邻且颜色相同的方块进行合并，合并后的新方块颜色不变，权重为两个方块的权重之和，合并成本为两个方块的权重之和。重复这个过程直到没有相邻同色方块可以合并。求将所有可能合并完成后的最小总成本。 解题过程： 问题分析： 我们需要合并相邻的同色方块，直到没有相邻方块颜色相同 每次合并的成本是合并的两个方块的权重之和 目标是找到所有可能合并序列中的最小总成本 这是一个区间动态规划问题，因为合并操作会影响相邻方块的关系 状态定义： 定义dp[ i][ j]表示合并区间[ i,j ]内的方块所需的最小成本。由于颜色会影响合并的可能性，我们还需要记录合并后区间的颜色信息。 状态转移方程： 考虑区间[ i,j ]： 如果区间内所有方块颜色相同，可以直接计算合并成本 否则，我们需要找到分割点k，将区间分为[ i,k]和[ k+1,j ] 当两个子区间合并后的颜色相同时，它们可以进一步合并 更精确的状态转移： dp[ i][ j] = min(dp[ i][ k] + dp[ k+1][ j] + cost) 对于所有i ≤ k < j 其中cost的计算需要考虑颜色是否相同 具体实现细节： 我们需要维护两个数组： dp[ i][ j]：区间[ i,j ]的最小合并成本 color[ i][ j]：区间[ i,j ]合并后的颜色（如果可合并） 状态转移： 对于每个区间[ i,j ]： 遍历所有分割点k ∈ [ i, j-1 ]： 如果color[ i][ k] == color[ k+1][ j ]： 总成本 = dp[ i][ k] + dp[ k+1][ j] + (sum_ weights[ i][ k] + sum_ weights[ k+1][ j ]) 更新dp[ i][ j ]为最小值 初始化： 单个方块的区间：dp[ i][ i] = 0，color[ i][ i ] = 方块i的颜色 区间和sum_ weights[ i][ j ]可以预处理得到 计算顺序： 按照区间长度从小到大计算： 先计算长度为1的区间 然后计算长度为2的区间 依此类推，直到计算整个区间[ 0,n-1 ] 时间复杂度：O(n³)，空间复杂度：O(n²) 这个问题的关键在于理解颜色约束对合并操作的影响，以及如何通过区间DP来考虑所有可能的合并顺序，找到成本最小的合并方案。