区间动态规划例题：合并相邻同色方块的最小成本问题

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

解题过程

让我们用区间DP来解决这个问题：

1. 定义状态
   设 dp[i][j] 表示合并区间 [i,j] 内所有可合并方块的最小成本。

2. 状态转移方程
   对于区间 [i,j]，我们需要考虑所有可能的分割点：

• 如果区间内所有方块颜色相同，直接合并整个区间
• 否则，枚举分割点 k，将区间分为 [i,k] 和 [k+1,j]

更精确的转移方程：
dp[i][j] = min(dp[i][k] + dp[k+1][j])，其中 i ≤ k < j

3. 预处理
   我们需要预处理每个区间的总权重，用 prefix_sum 数组：
   prefix_sum[i] 表示前 i 个方块的权重和
   区间 [i,j] 的总权重 = prefix_sum[j] - prefix_sum[i-1]

4. 边界条件

• 当 i = j 时，dp[i][j] = 0（单个方块不需要合并）
• 当区间内所有方块颜色相同时，dp[i][j] = 区间总权重（一次性合并整个区间）

具体实现步骤

def min_merge_cost(colors, weights):
    n = len(colors)
    
    # 预处理前缀和
    prefix = [0] * (n + 1)
    for i in range(1, n + 1):
        prefix[i] = prefix[i-1] + weights[i-1]
    
    # 初始化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  # 区间终点
            
            # 如果整个区间颜色相同
            if all_same_color(colors, i, j):
                dp[i][j] = prefix[j+1] - prefix[i]
            else:
                dp[i][j] = float('inf')
                # 枚举所有分割点
                for k in range(i, j):
                    cost = dp[i][k] + dp[k+1][j]
                    # 如果分割后的两个区间可以继续合并
                    if colors[k] == colors[k+1]:
                        cost += (prefix[k+1] - prefix[i]) + (prefix[j+1] - prefix[k+1])
                    dp[i][j] = min(dp[i][j], cost)
    
    return dp[0][n-1]

def all_same_color(colors, i, j):
    """检查区间[i,j]内所有颜色是否相同"""
    first_color = colors[i]
    for idx in range(i + 1, j + 1):
        if colors[idx] != first_color:
            return False
    return True

优化版本

上面的基础版本可以进一步优化，考虑颜色相同的连续区间：

def min_merge_cost_optimized(colors, weights):
    n = len(colors)
    
    # 预处理前缀和
    prefix = [0] * (n + 1)
    for i in range(1, n + 1):
        prefix[i] = prefix[i-1] + weights[i-1]
    
    # 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):
                left_cost = dp[i][k]
                right_cost = dp[k+1][j]
                
                total_cost = left_cost + right_cost
                
                # 如果分割点两侧颜色相同，可能需要额外合并
                if colors[k] == colors[k+1]:
                    # 计算合并成本
                    merge_cost = (prefix[k+1] - prefix[i]) + (prefix[j+1] - prefix[k+1])
                    total_cost += merge_cost
                
                dp[i][j] = min(dp[i][j], total_cost)
    
    return dp[0][n-1]

示例说明

假设有方块序列：
颜色: [1, 2, 2, 1]
权重: [1, 2, 3, 4]

计算过程：

1. 区间 [1,2]（颜色2,2）可以合并，成本 = 2+3 = 5
2. 区间 [0,3] 的最小成本通过枚举分割点得到
3. 最终找到最优合并顺序

时间复杂度

• 时间复杂度：O(n³)，需要三重循环
• 空间复杂度：O(n²)，用于存储DP表

这种方法确保了我们在所有可能的合并顺序中找到成本最小的方案。