石子合并是区间动态规划（Interval DP）的经典问题。给定一排 $n$ 堆石子，每堆石子有一定数量，要求通过 $n-1$ 次合并将它们合并成一堆。每次合并只能合并相邻的两堆，合并代价为两堆石子数之和，求最小（或最大）的总合并代价。本文用Java实现基于区间DP的解法，并探讨四边形不等式优化。
问题分析
问题描述：$n$ 堆石子排成一排，第 $i$ 堆有 $a_i$ 个石子。每次合并选择相邻的两堆合并为一堆，新堆的石子数为两堆之和，代价也为两堆之和。经过 $n-1$ 次合并后成为一堆，求最小总代价。
关键性质：无论以何种顺序合并，最终所有石子的总和都是 $\sum a_i$。不同的是合并的顺序会影响中间代价的累加次数——越早合并的石子，其值被累加的次数越多。
算法核心思想
区间DP状态定义
设 $dp[i][j]$ 表示将第 $i$ 堆到第 $j$ 堆石子合并成一堆的最小代价。前缀和 $sum[i]$ 表示前 $i$ 堆石子的总数。
状态转移方程：
$$dp[i][j] = \min_{i \le k < j} { dp[i][k] + dp[k+1][j] } + sum[j] – sum[i-1]$$
其中 $k$ 是分割点，表示先在 $k$ 处将区间 $[i,j]$ 分成两部分分别合并，最后再将两部分合并。
四边形不等式优化
当石子合并问题满足四边形不等式时，可以使用Knuth优化将时间复杂度从 $O(n^3)$ 降低到 $O(n^2)$。
设 $opt[i][j]$ 为区间 $[i,j]$ 的最优分割点，四边形不等式保证了：
$$opt[i][j-1] \le opt[i][j] \le opt[i+1][j]$$
这意味着在枚举分割点 $k$ 时，只需在 $[opt[i][j-1], opt[i+1][j]]$ 范围内搜索，大大减少了搜索空间。
Java完整实现
import java.util.Arrays;
/**
* 石子合并问题 - 区间动态规划实现
* 求将n堆石子合并成一堆的最小/最大代价
*/
public class StoneMerge {
/**
* 基础区间DP解法：O(n^3)
* @param stones 每堆石子的数量
* @return 最小总合并代价
*/
public static int minCostBasic(int[] stones) {
int n = stones.length;
if (n <= 1) {
return 0;
}
// 前缀和：sum[i] 表示前i堆石子的总数（1-based）
int[] prefixSum = new int[n + 1];
for (int i = 1; i <= n; i++) {
prefixSum[i] = prefixSum[i - 1] + stones[i - 1];
}
// dp[i][j]：将第i堆到第j堆合并的最小代价
int[][] dp = new int[n + 1][n + 1];
// 初始化：单个石子的合并代价为0
for (int i = 1; i <= n; i++) {
Arrays.fill(dp[i], Integer.MAX_VALUE / 2);
dp[i][i] = 0;
}
// 按区间长度从小到大枚举
for (int len = 2; len <= n; len++) {
for (int i = 1; i + len - 1 <= n; i++) {
int j = i + len - 1;
// 枚举分割点k
for (int k = i; k < j; k++) {
int cost = dp[i][k] + dp[k + 1][j] + prefixSum[j] - prefixSum[i - 1];
dp[i][j] = Math.min(dp[i][j], cost);
}
}
}
return dp[1][n];
}
/**
* 四边形不等式优化：O(n^2)
* 适用于满足四边形不等式的石子合并问题
*/
public static int minCostOptimized(int[] stones) {
int n = stones.length;
if (n <= 1) {
return 0;
}
int[] prefixSum = new int[n + 1];
for (int i = 1; i <= n; i++) {
prefixSum[i] = prefixSum[i - 1] + stones[i - 1];
}
int[][] dp = new int[n + 2][n + 2];
// opt[i][j] 记录区间[i,j]的最优分割点
int[][] opt = new int[n + 2][n + 2];
for (int i = 1; i <= n; i++) {
Arrays.fill(dp[i], Integer.MAX_VALUE / 2);
dp[i][i] = 0;
opt[i][i] = i; // 单个元素的分割点就是自身
}
for (int len = 2; len <= n; len++) {
for (int i = 1; i + len - 1 <= n; i++) {
int j = i + len - 1;
// 利用四边形不等式缩小搜索范围
int start = opt[i][j - 1];
int end = opt[i + 1][j];
for (int k = start; k <= end && k < j; k++) {
int cost = dp[i][k] + dp[k + 1][j] + prefixSum[j] - prefixSum[i - 1];
if (cost < dp[i][j]) {
dp[i][j] = cost;
opt[i][j] = k;
}
}
}
}
return dp[1][n];
}
/**
* 求最大合并代价
*/
public static int maxCost(int[] stones) {
int n = stones.length;
if (n <= 1) {
return 0;
}
int[] prefixSum = new int[n + 1];
for (int i = 1; i <= n; i++) {
prefixSum[i] = prefixSum[i - 1] + stones[i - 1];
}
int[][] dp = new int[n + 1][n + 1];
for (int len = 2; len <= n; len++) {
for (int i = 1; i + len - 1 <= n; i++) {
int j = i + len - 1;
dp[i][j] = Integer.MIN_VALUE;
for (int k = i; k < j; k++) {
int cost = dp[i][k] + dp[k + 1][j] + prefixSum[j] - prefixSum[i - 1];
dp[i][j] = Math.max(dp[i][j], cost);
}
}
}
return dp[1][n];
}
/**
* 打印最优合并方案（回溯）
*/
public static void printOptimalMerge(int[] stones) {
int n = stones.length;
int[] prefixSum = new int[n + 1];
for (int i = 1; i <= n; i++) {
prefixSum[i] = prefixSum[i - 1] + stones[i - 1];
}
int[][] dp = new int[n + 1][n + 1];
int[][] split = new int[n + 1][n + 1];
for (int i = 1; i <= n; i++) {
Arrays.fill(dp[i], Integer.MAX_VALUE / 2);
dp[i][i] = 0;
}
for (int len = 2; len <= n; len++) {
for (int i = 1; i + len - 1 <= n; i++) {
int j = i + len - 1;
for (int k = i; k < j; k++) {
int cost = dp[i][k] + dp[k + 1][j] + prefixSum[j] - prefixSum[i - 1];
if (cost < dp[i][j]) {
dp[i][j] = cost;
split[i][j] = k;
}
}
}
}
System.out.println("最小总代价: " + dp[1][n]);
System.out.println("最优合并顺序:");
printMergeOrder(split, 1, n, 1);
}
private static void printMergeOrder(int[][] split, int i, int j, int depth) {
if (i == j) {
System.out.println(" ".repeat(depth) + "石子[" + i + "]");
return;
}
int k = split[i][j];
System.out.println(" ".repeat(depth) + "合并区间 [" + i + "," + j + "] 在 " + k + " 处分割");
printMergeOrder(split, i, k, depth + 1);
printMergeOrder(split, k + 1, j, depth + 1);
}
/**
* 环形石子合并（首尾相连）
*/
public static int circularMinCost(int[] stones) {
int n = stones.length;
// 将数组复制一倍，破环成链
int[] doubled = new int[2 * n];
for (int i = 0; i < 2 * n; i++) {
doubled[i] = stones[i % n];
}
int[] prefixSum = new int[2 * n + 1];
for (int i = 1; i <= 2 * n; i++) {
prefixSum[i] = prefixSum[i - 1] + doubled[i - 1];
}
int[][] dp = new int[2 * n + 1][2 * n + 1];
for (int i = 1; i <= 2 * n; i++) {
Arrays.fill(dp[i], Integer.MAX_VALUE / 2);
dp[i][i] = 0;
}
for (int len = 2; len <= n; len++) {
for (int i = 1; i + len - 1 <= 2 * n; i++) {
int j = i + len - 1;
for (int k = i; k < j; k++) {
int cost = dp[i][k] + dp[k + 1][j] + prefixSum[j] - prefixSum[i - 1];
dp[i][j] = Math.min(dp[i][j], cost);
}
}
}
// 在2n个位置中找到最小值
int minCost = Integer.MAX_VALUE;
for (int i = 1; i <= n; i++) {
minCost = Math.min(minCost, dp[i][i + n - 1]);
}
return minCost;
}
public static void main(String[] args) {
int[] stones = {3, 2, 4, 1, 5};
System.out.println("=== 石子合并问题 ===");
System.out.println("石子数量: " + Arrays.toString(stones));
System.out.println("石子总数: " + Arrays.stream(stones).sum());
System.out.println();
System.out.println("基础DP最小代价: " + minCostBasic(stones));
System.out.println("优化DP最小代价: " + minCostOptimized(stones));
System.out.println("最大合并代价: " + maxCost(stones));
System.out.println();
printOptimalMerge(stones);
System.out.println("\n环形石子合并最小代价: " + circularMinCost(stones));
}
}
时间复杂度分析
| 解法 | 时间复杂度 | 空间复杂度 | 适用条件 |
|---|---|---|---|
| 基础区间DP | $O(n^3)$ | $O(n^2)$ | 通用 |
| 四边形不等式优化 | $O(n^2)$ | $O(n^2)$ | 满足四边形不等式 |
| 环形扩展 | $O((2n)^3) = O(n^3)$ | $O(n^2)$ | 环形排列 |
四边形不等式优化的核心在于：对于区间DP，若代价函数满足 $w(a,c) + w(b,d) \le w(a,d) + w(b,c)$（四边形不等式）和 $w(b,c) \le w(a,d)$（区间单调性），则最优决策点具有单调性，可以将内层枚举范围缩小。
算法拓展
石子合并问题的核心思想可推广到：
– 矩阵链乘：最优括号化方案（完全相同的DP框架）
– 最优二叉搜索树：构建访问代价最小的BST
– 凸多边形三角剖分：最小权重三角剖分
– 文件最优合并：哈夫曼编码的变体
– 字符串折叠：将重复子串折叠表示的最小长度
