合并相邻同色方块的最小成本问题（进阶版） 题目描述 给定一个由不同颜色方块组成的数组，每个方块有一个颜色值和一个权重值。每次操作可以选择两个相邻且颜色相同的方块进行合并，合并后的新方块颜色不变，权重为两个方块的权重之和，合并成本为两个方块的权重之和。重复这个过程直到无法合并为止。请计算将所有可合并的方块合并后的最小总成本。 解题过程 问题分析 这个问题需要在数组上不断合并相邻同色方块，目标是使总成本最小。由于合并顺序会影响最终结果，我们需要找到最优的合并顺序。这符合区间动态规划的特征，因为每个合并操作可以看作是对一个子区间的处理。 状态定义 定义 dp[i][j] 表示合并区间 [i,j] 内所有可合并方块的最小成本。同时，我们需要记录合并后的状态，因此定义 color[i][j] 表示区间 [i,j] 合并后的颜色， weight[i][j] 表示区间 [i,j] 合并后的总权重。 状态转移方程 对于区间 [i,j] ，考虑所有可能的分割点 k （ i ≤ k < j ）： 如果 color[i][k] == color[k+1][j] ，说明这两个子区间可以继续合并： dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + weight[i][k] + weight[k+1][j]) color[i][j] = color[i][k] （或 color[k+1][j] ，两者相同） weight[i][j] = weight[i][k] + weight[k+1][j] 如果颜色不同，则不能合并： dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j]) 初始化 对于长度为1的区间（ i = j ）： dp[i][i] = 0 （单个方块无需合并） color[i][i] = 该方块的颜色 weight[i][i] = 该方块的权重 计算顺序 按照区间长度从小到大计算： 先计算所有长度为2的区间 然后计算长度为3的区间 依此类推，直到计算整个区间 [0,n-1] 最终结果 最终答案为 dp[0][n-1] ，即合并整个数组的最小成本。 举例说明 考虑数组：[ (红色, 2), (蓝色, 3), (蓝色, 1), (红色, 4) ] 计算过程： 初始化：所有长度为1的区间成本为0 长度为2的区间： [ 0,1 ]：颜色不同，不能合并，成本=0 [ 1,2 ]：颜色相同，合并成本=3+1=4 [ 2,3 ]：颜色不同，不能合并，成本=0 长度为3的区间： [ 0,2]：考虑分割点k=1，[ 0,1]和[ 2,2 ]颜色不同，成本=0+0=0 [ 1,3]：考虑分割点k=1，[ 1,1]和[ 2,3 ]颜色不同，成本=0+0=0 长度为4的区间[ 0,3 ]： 考虑所有分割点，找到最优解为： 先合并[ 1,2 ]（成本4），再与相邻同色方块合并 通过这样的递推计算，最终得到最小总成本。