【题目描述】

在一个操场上一排地摆放着N堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的2堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。

设计一个程序，计算出将N堆石子合并成一堆的最小得分。

【输入描述】

第一行为一个正整数N (2≤N≤100)；

以下N行,每行一个正整数，小于10000，分别表示第i堆石子的个数（1≤i≤N）。

【输出描述】

【样例输入】

7
13
7
8
16
21
4
18

【样例输出】

239

【题目分析】

1.定义状态：

设 dp[i][j] 表示合并第 i 堆到第 j 堆石子的最小得分。

为了方便计算区间和，预处理一个前缀和数组 sum，其中 sum[i] 表示前 i 堆石子的总数。

2.状态转移方程：

对于区间 [i, j]，枚举最后一次合并的分割点 k（i ≤ k < j），将区间分成 [i, k] 和 [k+1, j]。

合并这两部分的得分为 sum[j] - sum[i-1]（即区间 [i, j] 的石子总数）。

状态转移方程为：

dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + sum[j] - sum[i - 1]);

3.初始化：

单个石堆不需要合并，因此 dp[i][i] = 0。

其他 dp[i][j] 初始化为一个较大值（如 INT_MAX）。

4.计算顺序：

按区间长度从小到大计算，因为长区间的结果依赖于短区间。

【参考答案】

#include <iostream>
#include <climits>
using namespace std;

const int MAX_N = 100;  // 最大石子堆数

int main() {
	int N;
	cin >> N;
	int stones[MAX_N + 1] = {0};  // 石子堆，从1开始编号
	int sum[MAX_N + 1] = {0};     // 前缀和数组
	for (int i = 1; i <= N; i++) {
		cin >> stones[i];
		sum[i] = sum[i - 1] + stones[i];
	}

	// DP表，dp[i][j]表示合并i到j堆的最小得分
	int dp[MAX_N + 1][MAX_N + 1] = {0};

	// 初始化：单个石堆不需要合并，得分为0
	for (int i = 1; i <= N; i++) {
		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;              // 区间终点
			dp[i][j] = INT_MAX;
			for (int k = i; k < j; k++) {     // 枚举分割点
				dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + sum[j] - sum[i - 1]);
			}
		}
	}

	cout << dp[1][N] << endl;
	return 0;
}