编辑代码

#include <iostream> 
#include <vector> 
#include <climits> 
using namespace std;
int stoneMerge(vector<int>& piles) {
	int n = piles.size();
	vector<vector<int>> dp(n, vector<int>(n, INT_MAX)); // dp[i][j]表示从第i堆到第j堆合并的最小代价 
	vector<int> prefixSum(n + 1, 0); // 前缀和数组，prefixSum[i]表示前i堆石子的总和 
	// 计算前缀和 
	for (int i = 0; i < n; ++i) {
		prefixSum[i + 1] = prefixSum[i] + piles[i];
	}
	// 初始化dp数组，单堆石子的合并代价为0 
	for (int i = 0; i < n; ++i) {
		dp[i][i] = 0;
	}
	// 填充dp数组 
	for (int len = 2; len <= n; ++len) { // 合并的堆数从2开始 
		for (int i = 0; i <= n - len; ++i) {
			int j = i + len - 1;
			for (int k = i; k < j; ++k) {
				dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + prefixSum[j + 1] - prefixSum[i]);
			}
		}
	}
	return dp[0][n - 1]; // 返回从第1堆到第n堆合并的最小代价 
}
int main() {
	// 示例1 
	std::vector<int> piles;
	int n;
	cin>> n;
	piles.resize(n); // 容器现在有5个元素，都是未初始化的 
	for (int i = 0;i < n;i++)
	{
		cin >> piles[i];
	}
	cout << "Example 1: " << stoneMerge(piles) << endl; // 输出: 9 
	// 示例2 
	vector<int> piles2 = { 13, 7, 8, 16, 21, 4, 18 };
	cout << "Example 2: " << stoneMerge(piles2) << endl; // 输出: 239 
	return 0;
}