合并相邻同色方块的最小成本问题（颜色扩展版） 题目描述： 给定一个由不同颜色方块组成的数组，每个方块有一个颜色值和一个权重值。每次操作可以选择两个相邻且颜色相同的方块进行合并，合并后的新方块颜色保持不变，权重为两个方块权重之和，合并成本为两个方块权重之和。重复这个过程直到无法合并，求最小总合并成本。 解题过程： 问题分析： 这是一个区间动态规划问题，因为合并操作具有重叠子问题特性 我们需要找到一种合并顺序，使得总成本最小 关键观察：合并时需要考虑颜色匹配，只有同色方块才能合并 状态定义： 定义dp[ i][ j]表示合并区间[ i,j ]内所有方块的最小成本 状态转移方程： 对于区间[ i,j ]，考虑所有可能的分割点k： 如果color[ i] = color[ k+1]，可以考虑将[ i,k]和[ k+1,j ]合并 转移方程：dp[ i][ j] = min(dp[ i][ j], dp[ i][ k] + dp[ k+1][ j] + sum[ i][ j ]) 其中sum[ i][ j]表示区间[ i,j ]内所有方块的权重和 特殊情况处理： 当区间长度为1时，dp[ i][ i ] = 0（不需要合并） 当区间内所有方块颜色相同时，可以直接合并 当区间内存在多种颜色时，需要找到最优的合并顺序 算法步骤： 步骤1：预处理前缀和数组，方便快速计算区间和 步骤2：初始化dp数组，对角线元素设为0 步骤3：按区间长度从小到大进行动态规划 步骤4：对于每个区间[ i,j ]，遍历所有可能的分割点k 步骤5：如果两端颜色匹配，更新dp值 步骤6：最终dp[ 0][ n-1 ]即为答案 时间复杂度：O(n³)，空间复杂度：O(n²) 这个问题的关键在于理解颜色约束对合并顺序的影响，以及如何通过区间DP找到最优的合并策略。