合并相邻同色方块的最小成本问题（进阶版） 题目描述： 给定一个由不同颜色方块组成的数组，每个方块有一个颜色值和一个权重值。每次操作可以选择两个相邻且颜色相同的方块进行合并，合并后的新方块颜色不变，权重为两个方块权重之和，合并成本为两个方块权重之和。重复这个过程直到没有相邻同色方块可合并。求将所有可合并方块合并后的最小总成本。 解题过程： 问题分析： 这是一个区间DP问题，因为合并操作会影响相邻方块的状态 关键观察：只有颜色相同的相邻方块才能合并 合并后新方块的权重会增加，可能创造新的合并机会 需要找到最优的合并顺序来最小化总成本 DP状态定义： 定义dp[ i][ j]表示合并区间[ i,j ]内的所有可合并方块的最小成本 定义sum[ i][ j]表示区间[ i,j ]内所有方块的权重和 状态转移方程： 对于区间[ i,j ]，考虑所有可能的分割点k： 如果color[ i] = color[ k+1]，可以考虑先分别合并[ i,k]和[ k+1,j ]，然后合并这两个区间 转移方程：dp[ i][ j] = min(dp[ i][ k] + dp[ k+1][ j] + sum[ i][ k] + sum[ k+1][ j])，其中color[ i] = color[ k+1 ] 但是这样还不够，因为可能中间有其他颜色的方块阻隔。我们需要更精细的处理。 改进的状态定义： 定义dp[ i][ j][ c]表示将区间[ i,j ]合并到颜色为c的单个方块的最小成本 但这可能状态太多，我们采用另一种方法： 定义dp[ i][ j]表示将区间[ i,j ]完全合并（直到不能再合并）的最小成本 定义f[ i][ j]表示区间[ i,j ]合并后的最终颜色（如果能够完全合并成一个方块） 详细的状态转移： 基础情况：当i=j时，dp[ i][ j]=0，f[ i][ j]=color[ i ] 对于i <j，考虑两种情况： a) 最后一步合并：如果存在k使得[ i,k]和[ k+1,j ]合并后的颜色相同，则可以合并 b) 先合并子区间，再考虑整体合并 更精确的转移： dp[ i][ j ] = min{ dp[ i][ k] + dp[ k+1][ j] + sum[ i][ k] + sum[ k+1][ j] (当f[ i][ k] = f[ k+1][ j ]时) dp[ i][ k] + dp[ k+1][ j ] (当不能直接合并，但需要分别计算成本时) } 预处理权重和： 我们可以预处理前缀和数组prefix，使得sum[ i][ j] = prefix[ j] - prefix[ i-1 ] 算法步骤： 步骤1：计算前缀和数组 步骤2：初始化dp和f数组 步骤3：按区间长度从小到大计算 步骤4：对于每个区间[ i,j ]，遍历所有分割点k 步骤5：如果左右区间合并后颜色相同，考虑合并的成本 步骤6：记录最小成本和最终颜色 时间复杂度：O(n³)，空间复杂度：O(n²) 边界情况处理： 单个方块：成本为0 没有相同颜色相邻方块：成本为0 所有方块颜色相同：退化为经典的合并石子问题 这个进阶版本相比基础版本，增加了颜色约束，使得合并操作只有在颜色匹配时才能进行，这增加了问题的复杂性，需要同时跟踪合并成本和最终颜色状态。