线性动态规划：石子合并（区间DP）

题目描述
有 N 堆石子排成一排，每堆石子有一定数量。现在要将这些石子合并成一堆。合并的规则是：每次只能合并相邻的两堆石子，合并的代价是这两堆石子的数量之和。求将所有石子合并成一堆的最小总代价。

例如：石子堆数量为 [4, 2, 3, 1]，合并顺序不同会导致总代价不同。目标是找到最小的总代价。

解题思路
这是一个经典的区间动态规划问题。关键点在于：

1. 最终合并成一堆的过程，可以看作是将初始区间 [1, N] 不断划分为子区间合并的结果。
2. 如果最后一次合并发生在将左区间 [i, k] 和右区间 [k+1, j] 合并，那么本次合并的代价是 sum(i, j)（即区间内所有石子数量之和），而左右区间各自合并的最小代价可以递归求解。
3. 因此可以用 dp[i][j] 表示合并区间 [i, j] 的最小代价。

详细步骤

1. 定义状态
dp[i][j] = 合并第 i 堆到第 j 堆（闭区间）的最小代价。
目标是求 dp[1][N]（假设堆编号从 1 开始）。

2. 状态转移方程
考虑最后一次合并：将 [i, k] 和 [k+1, j] 两堆合并（i ≤ k < j）。
合并 [i, j] 的代价 = dp[i][k] + dp[k+1][j] + sum(i, j)。
其中 sum(i, j) 是区间内石子总数，可以提前用前缀和计算。
所以：

dp[i][j] = min{ dp[i][k] + dp[k+1][j] + sum(i, j) | i ≤ k < j }

当 i == j 时，只有一堆石子，不需要合并，代价为 0。

3. 计算顺序
因为大区间依赖于更小的区间，所以应按区间长度从小到大计算：
先计算所有长度为 2 的区间，再长度 3，直到长度 N。

4. 前缀和优化
为了快速得到 sum(i, j)，预处理前缀和数组 prefix：
prefix[i] 表示前 i 堆石子的总数量，则 sum(i, j) = prefix[j] - prefix[i-1]。

5. 初始化
dp[i][i] = 0（单独一堆无需合并）。
其他 dp[i][j] 初始化为一个较大值（如 INF），以便取最小值。

举例说明
石子数量：[4, 2, 3, 1]，N = 4。

前缀和：prefix = [0, 4, 6, 9, 10]（prefix[0]=0，prefix[1]=4，…）。

计算过程：

• 长度 = 1：dp[1][1]=0, dp[2][2]=0, dp[3][3]=0, dp[4][4]=0。
• 长度 = 2：
  • dp[1][2]：k=1，dp[1][1]+dp[2][2]+sum(1,2)=0+0+(6-0)=6。
  • dp[2][3]：k=2，dp[2][2]+dp[3][3]+sum(2,3)=0+0+(9-4)=5。
  • dp[3][4]：k=3，dp[3][3]+dp[4][4]+sum(3,4)=0+0+(10-6)=4。
• 长度 = 3：
  • dp[1][3]：
    • k=1：dp[1][1]+dp[2][3]+sum(1,3)=0+5+(9-0)=14
    • k=2：dp[1][2]+dp[3][3]+sum(1,3)=6+0+9=15
      取 min = 14。
  • dp[2][4]：
    • k=2：dp[2][2]+dp[3][4]+sum(2,4)=0+4+(10-4)=10
    • k=3：dp[2][3]+dp[4][4]+sum(2,4)=5+0+6=11
      取 min = 10。
• 长度 = 4：dp[1][4]
  • k=1：dp[1][1]+dp[2][4]+sum(1,4)=0+10+10=20
  • k=2：dp[1][2]+dp[3][4]+sum(1,4)=6+4+10=20
  • k=3：dp[1][3]+dp[4][4]+sum(1,4)=14+0+10=24
    取 min = 20。

最终结果：dp[1][4] = 20。

时间复杂度与空间复杂度

• 状态数：O(N²)
• 每个状态需枚举分割点 k，O(N)
• 总复杂度 O(N³)（N 一般 ≤ 300 可接受）
• 空间复杂度 O(N²)

代码框架（Python）

def min_cost_to_merge_stones(stones):
    n = len(stones)
    prefix = [0] * (n + 1)
    for i in range(1, n + 1):
        prefix[i] = prefix[i - 1] + stones[i - 1]
    
    dp = [[0] * (n + 1) for _ in range(n + 1)]
    # 初始化 dp[i][i] = 0 已默认
    
    for length in range(2, n + 1):          # 区间长度
        for i in range(1, n - length + 2):  # 左端点
            j = i + length - 1              # 右端点
            dp[i][j] = float('inf')
            for k in range(i, j):           # 分割点
                cost = dp[i][k] + dp[k + 1][j] + (prefix[j] - prefix[i - 1])
                dp[i][j] = min(dp[i][j], cost)
    
    return dp[1][n]

# 示例
stones = [4, 2, 3, 1]
print(min_cost_to_merge_stones(stones))  # 输出 20

关键点总结

1. 区间 DP 的典型模式：枚举区间长度、左端点、分割点。
2. 合并代价是区间总和，用前缀和快速计算。
3. 注意区间边界和下标处理，避免出错。

变种与扩展
本题是基础的“相邻合并”问题。还有变种如：

• 石子排成环形（处理方式：将数组复制一份接在后面，最后取所有长度为 N 的区间最小值）。
• 每次合并相邻的 K 堆（此时需另加一维状态表示当前区间合并成几堆）。

但本次讲解限于基础线性（区间）DP，掌握核心状态转移即可。