#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));
vector<int> prefixSum(n + 1, 0);
for (int i = 0; i < n; ++i) {
prefixSum[i + 1] = prefixSum[i] + piles[i];
}
for (int i = 0; i < n; ++i) {
dp[i][i] = 0;
}
for (int len = 2; len <= n; ++len) {
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];
}
int main() {
vector<int> piles1 = {1, 2, 3};
cout << "Example 1: " << stoneMerge(piles1) << endl;
vector<int> piles2 = {13, 7, 8, 16, 21, 4, 18};
cout << "Example 2: " << stoneMerge(piles2) << endl;
return 0;
}