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

题目描述：
给定一个长度为n的颜色数组colors和一个成本数组costs，其中colors[i]表示第i个方块的颜色，costs[i]表示移除第i个方块的成本。你可以执行以下操作任意次：选择一组连续的相同颜色的方块（长度至少为2），移除这组方块，移除成本为这组方块的成本之和。求移除所有方块的最小总成本。

解题过程：

1. 问题分析：

• 这是一个区间消除类问题，每次只能移除连续的同色方块
• 移除后相邻的方块会拼接在一起
• 目标是找到最优的移除顺序，使得总成本最小

2. 状态定义：
   定义dp[i][j]表示移除区间[i, j]内所有方块的最小成本

3. 基础情况：

• 当i > j时，dp[i][j] = 0（空区间）
• 当i = j时，dp[i][j] = 0（单个方块不能单独移除）

4. 状态转移方程：
   考虑区间[i, j]的移除策略：

情况1：将区间分成两部分分别移除
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j])，其中i ≤ k < j

情况2：当colors[i] == colors[j]时，可以考虑将区间[i, j]与中间的某些同色方块一起移除

• 如果colors[i] == colors[k]（i < k ≤ j），我们可以先移除[i+1, k-1]和[k+1, j]，最后将i和k一起移除
• 更通用的写法：dp[i][j] = min(dp[i][j], dp[i+1][k-1] + dp[k+1][j])，其中colors[i] == colors[k]

5. 具体实现步骤：
   步骤1：预处理前缀和数组，方便计算区间成本
   步骤2：按区间长度从小到大进行动态规划
   步骤3：对于每个区间[i, j]，考虑所有可能的分割点
   步骤4：特别处理首尾颜色相同的情况

6. 算法实现：

def minCostToRemoveBlocks(colors, costs):
    n = len(colors)
    if n == 0:
        return 0
    
    # 前缀和数组
    prefix = [0] * (n + 1)
    for i in range(n):
        prefix[i+1] = prefix[i] + costs[i]
    
    # DP数组初始化
    dp = [[0] * n for _ in range(n)]
    
    # 按区间长度遍历
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            
            # 初始化为将区间分成两部分的最小值
            dp[i][j] = float('inf')
            for k in range(i, j):
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j])
            
            # 如果首尾颜色相同，考虑一起移除
            if colors[i] == colors[j]:
                # 先移除中间部分，最后一起移除首尾
                dp[i][j] = min(dp[i][j], dp[i+1][j-1])
                
                # 考虑中间有相同颜色的情况
                for k in range(i + 1, j):
                    if colors[i] == colors[k]:
                        dp[i][j] = min(dp[i][j], dp[i+1][k-1] + dp[k+1][j])
    
    return dp[0][n-1]

7. 优化思路：

• 可以记录每个位置后面同色方块的位置，减少不必要的循环
• 使用记忆化搜索可能更直观

8. 时间复杂度：O(n³)
9. 空间复杂度：O(n²)

这个问题的关键在于理解：当首尾颜色相同时，我们可以通过合理的移除顺序，让首尾方块在最后一起被移除，从而可能获得更小的移除成本。