合并相邻同色方块的最小成本问题

题目描述：
给定一个由不同颜色方块组成的序列，每个方块有一个颜色值。每次操作可以选择两个相邻且颜色相同的方块进行合并，合并后的新方块颜色不变，但会产生一个成本，成本等于这两个方块的颜色值之和。合并后的新方块会与相邻方块形成新的相邻关系。重复这个过程直到没有可以合并的方块为止。求将所有可能合并完成后的最小总成本。

解题过程：

1. 问题分析
这是一个典型的区间动态规划问题。我们需要找到一个合并顺序，使得总成本最小。关键观察是：合并操作会改变序列结构，但最终结果是一个没有相邻同色方块的序列。

2. 状态定义
定义 dp[i][j] 表示处理区间 [i, j] 的最小成本。但是仅用这个状态还不够，因为我们需要知道合并后区间两端的情况。

更好的状态定义：

• dp[i][j][0]：将区间 [i, j] 合并后的最小成本
• dp[i][j][1]：区间 [i, j] 合并后的颜色值（如果区间内所有方块颜色相同）或一个特殊值表示区间内颜色不一致

3. 状态转移方程

情况1：如果区间内所有方块颜色相同

• 那么我们可以一次性合并所有方块
• 合并成本 = 方块颜色值 × (区间长度 - 1)
• dp[i][j][0] = color × (j - i)
• dp[i][j][1] = color

情况2：如果区间内颜色不一致

• 我们需要找到分割点k，将区间分为 [i, k] 和 [k+1, j]
• 如果左右两个子区间合并后的颜色相同，那么可以继续合并
• dp[i][j][0] = min(dp[i][k][0] + dp[k+1][j][0] + (如果颜色相同则加上合并成本))
• dp[i][j][1] = (如果颜色相同则为该颜色，否则为不一致标记)

4. 具体算法步骤

步骤1：预处理

• 读取输入序列和颜色值
• 初始化dp数组为无穷大

步骤2：处理长度为1的区间

• 对于每个i，dp[i][i][0] = 0（单个方块不需要合并）
• dp[i][i][1] = colors[i]（单个方块的颜色）

步骤3：按区间长度从小到大处理

• 对于长度len从2到n

• 对于起始位置i从0到n-len

• 计算结束位置j = i + len - 1

  情况A：如果整个区间颜色相同

  if all colors in [i,j] are the same:
      dp[i][j][0] = color * (len - 1)
      dp[i][j][1] = color
  

  情况B：区间颜色不同，枚举分割点

  for k in range(i, j):
      cost = dp[i][k][0] + dp[k+1][j][0]
      left_color = dp[i][k][1]
      right_color = dp[k+1][j][1]
  
      # 如果左右区间合并后颜色相同，可以继续合并
      if left_color == right_color and left_color != -1:
          cost += left_color  # 合并成本
          dp[i][j][0] = min(dp[i][j][0], cost)
          dp[i][j][1] = left_color
      else:
          dp[i][j][0] = min(dp[i][j][0], cost)
          # 颜色标记为不一致
          dp[i][j][1] = -1
  

步骤4：返回结果

• 最终答案是 dp[0][n-1][0]

5. 示例演示

考虑序列：[2, 2, 3, 3]

初始状态：

• dp[0][0] = (0, 2), dp[1][1] = (0, 2)
• dp[2][2] = (0, 3), dp[3][3] = (0, 3)

长度2的区间：

长度4的区间[0,3]：

• 分割点k=1: 0,1和2,3
  • 左区间颜色=2，右区间颜色=3，颜色不同
  • 成本=2+3=5
• 这是唯一的分割方式
• 最终最小成本=5

6. 复杂度分析

• 时间复杂度：O(n³)，需要枚举所有区间和分割点
• 空间复杂度：O(n²)，用于存储dp数组

7. 优化思路
可以通过预处理来快速判断区间内是否所有颜色相同，使用前缀和或区间查询数据结构来优化判断过程。