区间动态规划例题：石子合并问题
题目描述
有N堆石子排成一排，每堆石子有一定的数量。现要将所有石子合并成一堆。合并的规则是：每次只能选择相邻的两堆石子合并成一堆，合并的代价是这两堆石子的数量之和。请设计一个算法，计算出将N堆石子合并成一堆的最小总代价。
例如：有4堆石子，数量依次为4, 5, 9, 4。
一种合并方案及其总代价计算如下：
- 合并前两堆 (4, 5)，代价 4+5=9，得到新石子堆序列 [9, 9, 4]（总代价=9）
- 合并后两堆 (9, 4)，代价 9+4=13，得到新序列 [9, 13]（总代价=9+13=22）
- 合并最后两堆 (9, 13)，代价 9+13=22，得到一堆 [22]（总代价=22+22=44）
总代价为44。但这是最优解吗？我们需要找到最小总代价。
解题过程
1. 问题分析
这是一个典型的区间动态规划问题。关键特征：
- 操作对象是线性排列的多个元素（石子堆）
- 每次操作针对相邻区间，合并后产生新元素
- 需要找到最优的操作顺序以最小化总代价
2. 定义状态
定义dp[i][j]表示将第i堆到第j堆石子合并成一堆的最小代价（1 ≤ i ≤ j ≤ N）。
最终目标是求dp[1][N]。
3. 状态转移方程
考虑最后一次合并：当合并[i,j]区间时，最后一步一定是将[i,k]和[k+1,j]两个区间合并（i ≤ k < j）。
因此：dp[i][j] = min(dp[i][k] + dp[k+1][j] + sum(i,j))，其中sum(i,j)是i到j堆石子的总数量（合并[i,k]和[k+1,j]的代价）。
4. 预处理前缀和
为了快速计算sum(i,j)，预处理前缀和数组prefix：
prefix[0] = 0, prefix[i] = stones[1] + stones[2] + ... + stones[i]
那么sum(i,j) = prefix[j] - prefix[i-1]
5. 计算顺序
由于大区间依赖小区间，需要按区间长度从小到大计算：
- 先计算所有长度为1的区间（dp[i][i] = 0，单堆无需合并）
- 再计算长度为2, 3, ..., N的区间
6. 详细计算示例（石子[4,5,9,4]）
前缀和：prefix = [0,4,9,18,22]（索引0~4）
长度=2：
- dp[1][2] = dp[1][1]+dp[2][2]+sum(1,2) = 0+0+(9-0)=9
- dp[2][3] = 0+0+(18-4)=14
- dp[3][4] = 0+0+(22-9)=13
长度=3：
- dp[1][3] = min(
k=1: dp[1][1]+dp[2][3]+sum(1,3) = 0+14+(18-0)=32,
k=2: dp[1][2]+dp[3][3]+sum(1,3) = 9+0+18=27
) = 27 - dp[2][4] = min(
k=2: dp[2][2]+dp[3][4]+sum(2,4) = 0+13+(22-4)=31,
k=3: dp[2][3]+dp[4][4]+sum(2,4) = 14+0+18=32
) = 31
长度=4：
dp[1][4] = min(
k=1: dp[1][1]+dp[2][4]+sum(1,4) = 0+31+22=53,
k=2: dp[1][2]+dp[3][4]+sum(1,4) = 9+13+22=44,
k=3: dp[1][3]+dp[4][4]+sum(1,4) = 27+0+22=49
) = 44
7. 算法实现
def stone_merge(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 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): # 分割点
cost = dp[i][k] + dp[k+1][j] + prefix[j+1]-prefix[i]
if cost < dp[i][j]:
dp[i][j] = cost
return dp[0][n-1]
8. 复杂度分析
时间复杂度：O(N³)（三层循环）
空间复杂度：O(N²)（DP表）
这个解法通过系统性地计算所有可能区间的最优解，保证了找到全局最优解。