## Approach 1: Top-down 3D DP

• Time:O(n^3)
• Space:O(Kn^2)

## C++

``````class Solution {
public:
int mergeStones(vector<int>& stones, int K) {
const int n = stones.size();
this->K = K;

// dp[i][j][k] := min cost to merge stones[i..j] into k piles
dp.resize(n, vector<vector<int>>(n, vector<int>(K + 1, kMax)));
prefix.resize(n + 1);

partial_sum(begin(stones), end(stones), begin(prefix) + 1);

const int cost = mergeStones(stones, 0, n - 1, 1);
return cost == kMax ? -1 : cost;
}

private:
constexpr static int kMax = 1e9;
int K;
vector<vector<vector<int>>> dp;
vector<int> prefix;

int mergeStones(const vector<int>& stones, int i, int j, int k) {
if ((j - i + 1 - k) % (K - 1))
return kMax;
if (i == j)
return k == 1 ? 0 : kMax;
if (dp[i][j][k] != kMax)
return dp[i][j][k];
if (k == 1)
return mergeStones(stones, i, j, K) + prefix[j + 1] - prefix[i];

for (int m = i; m < j; m += K - 1)
dp[i][j][k] = min(dp[i][j][k], mergeStones(stones, i, m, 1) +
mergeStones(stones, m + 1, j, k - 1));

return dp[i][j][k];
}
};
``````

## JAVA

``````class Solution {
public int mergeStones(int[] stones, int K) {
final int n = stones.length;
this.K = K;

// dp[i][j][k] := min cost to merge stones[i..j] into k piles
dp = new int[n][n][K + 1];
for (int[][] A : dp)
Arrays.stream(A).forEach(a -> Arrays.fill(a, kMax));
prefix = new int[n + 1];

for (int i = 0; i < n; ++i)
prefix[i + 1] = prefix[i] + stones[i];

final int cost = mergeStones(stones, 0, n - 1, 1);
return cost == kMax ? -1 : cost;
}

private static final int kMax = (int) 1e9;
private int K;
private int[][][] dp;
private int[] prefix;

private int mergeStones(final int[] stones, int i, int j, int k) {
if ((j - i + 1 - k) % (K - 1) != 0)
return kMax;
if (i == j)
return k == 1 ? 0 : kMax;
if (dp[i][j][k] != kMax)
return dp[i][j][k];
if (k == 1)
return mergeStones(stones, i, j, K) + prefix[j + 1] - prefix[i];

for (int m = i; m < j; m += K - 1)
dp[i][j][k] = Math.min(
dp[i][j][k],
mergeStones(stones, i, m, 1) +
mergeStones(stones, m + 1, j, k - 1));

return dp[i][j][k];
}
}
``````

## Approach 2: Bottom-up 3D DP

• Time:O(n^3)
• Space:O(Kn^2)

## C++

``````class Solution {
public:
int mergeStones(vector<int>& stones, int K) {
const int n = stones.size();
if ((n - 1) % (K - 1))
return -1;

constexpr int kMax = 1e9;

// dp[i][j][k] := min cost to merge stones[i..j] into k piles
vector<vector<vector<int>>> dp(
n, vector<vector<int>>(n, vector<int>(K + 1, kMax)));
vector<int> prefix(n + 1);

for (int i = 0; i < n; ++i)
dp[i][i][1] = 0;

partial_sum(begin(stones), end(stones), begin(prefix) + 1);

for (int d = 1; d < n; ++d)
for (int i = 0; i + d < n; ++i) {
const int j = i + d;
for (int k = 2; k <= K; ++k)  // piles
for (int m = i; m < j; m += K - 1)
dp[i][j][k] = min(dp[i][j][k], dp[i][m][1] + dp[m + 1][j][k - 1]);
dp[i][j][1] = dp[i][j][K] + prefix[j + 1] - prefix[i];
}

return dp[0][n - 1][1];
}
};
``````

## JAVA

``````class Solution {
public int mergeStones(int[] stones, int K) {
final int n = stones.length;
if ((n - 1) % (K - 1) != 0)
return -1;

final int kMax = (int) 1e9;

// dp[i][j][k] := min cost to merge stones[i..j] into k piles
int[][][] dp = new int[n][n][K + 1];
for (int[][] A : dp)
Arrays.stream(A).forEach(a -> Arrays.fill(a, kMax));
int[] prefix = new int[n + 1];

for (int i = 0; i < n; ++i)
dp[i][i][1] = 0;

for (int i = 0; i < n; ++i)
prefix[i + 1] = prefix[i] + stones[i];

for (int d = 1; d < n; ++d)
for (int i = 0; i + d < n; ++i) {
final int j = i + d;
for (int k = 2; k <= K; ++k) // piles
for (int m = i; m < j; m += K - 1)
dp[i][j][k] = Math.min(dp[i][j][k], dp[i][m][1] + dp[m + 1][j][k - 1]);
dp[i][j][1] = dp[i][j][K] + prefix[j + 1] - prefix[i];
}

return dp[0][n - 1][1];
}
}
``````

## Approach 3: Top-down 2D DP

• Time:O(n^3 / K)
• Space:O(n^2)

## C++

``````class Solution {
public:
int mergeStones(vector<int>& stones, int K) {
const int n = stones.size();
if ((n - 1) % (K - 1))
return -1;

this->K = K;

// dp[i][j] := min cost to merge stones[i..j]
dp.resize(n, vector<int>(n, kMax));
prefix.resize(n + 1);

partial_sum(begin(stones), end(stones), begin(prefix) + 1);

const int cost = mergeStones(stones, 0, n - 1);
return cost == kMax ? -1 : cost;
}

private:
constexpr static int kMax = 1e9;
int K;
vector<vector<int>> dp;
vector<int> prefix;

int mergeStones(const vector<int>& stones, int i, int j) {
if (j - i + 1 < K)
return 0;
if (dp[i][j] != kMax)
return dp[i][j];

for (int m = i; m < j; m += K - 1)
dp[i][j] = min(dp[i][j],
mergeStones(stones, i, m) + mergeStones(stones, m + 1, j));
if ((j - i) % (K - 1) == 0)
dp[i][j] += prefix[j + 1] - prefix[i];

return dp[i][j];
}
};
``````

## JAVA

``````class Solution {
public int mergeStones(int[] stones, int K) {
final int n = stones.length;
if ((n - 1) % (K - 1) != 0)
return -1;

this.K = K;

// dp[i][j] := min cost to merge stones[i..j]
dp = new int[n][n];
Arrays.stream(dp).forEach(A -> Arrays.fill(A, kMax));
prefix = new int[n + 1];

for (int i = 0; i < n; ++i)
prefix[i + 1] = prefix[i] + stones[i];

final int cost = mergeStones(stones, 0, n - 1);
return cost == kMax ? -1 : cost;
}

private static final int kMax = (int) 1e9;
private int K;
private int[][] dp;
private int[] prefix;

private int mergeStones(final int[] stones, int i, int j) {
if (j - i + 1 < K)
return 0;
if (dp[i][j] != kMax)
return dp[i][j];

for (int m = i; m < j; m += K - 1)
dp[i][j] = Math.min(dp[i][j], mergeStones(stones, i, m) + mergeStones(stones, m + 1, j));
if ((j - i) % (K - 1) == 0)
dp[i][j] += prefix[j + 1] - prefix[i];

return dp[i][j];
}
}
``````

## Approach 4: Bottom-up 2D DP

• Time:O(n^3 / K)
• Space:O(n^2)

## C++

``````class Solution {
public:
int mergeStones(vector<int>& stones, int K) {
const int n = stones.size();
if ((n - 1) % (K - 1))
return -1;

constexpr int kMax = 1e9;

// dp[i][j] := min cost to merge stones[i..j]
vector<vector<int>> dp(n, vector<int>(n, kMax));
vector<int> prefix(n + 1);

for (int i = 0; i < n; ++i)
dp[i][i] = 0;

partial_sum(begin(stones), end(stones), begin(prefix) + 1);

for (int d = 1; d < n; ++d)
for (int i = 0; i + d < n; ++i) {
const int j = i + d;
for (int m = i; m < j; m += K - 1)
dp[i][j] = min(dp[i][j], dp[i][m] + dp[m + 1][j]);
if (d % (K - 1) == 0)
dp[i][j] += prefix[j + 1] - prefix[i];
}

return dp[0][n - 1];
}
};
``````

## JAVA

``````class Solution {
public int mergeStones(int[] stones, int K) {
final int n = stones.length;
if ((n - 1) % (K - 1) != 0)
return -1;

final int kMax = (int) 1e9;

// dp[i][j] := min cost to merge stones[i..j]
int[][] dp = new int[n][n];
Arrays.stream(dp).forEach(A -> Arrays.fill(A, kMax));
int[] prefix = new int[n + 1];

for (int i = 0; i < n; ++i)
dp[i][i] = 0;

for (int i = 0; i < n; ++i)
prefix[i + 1] = prefix[i] + stones[i];

for (int d = 1; d < n; ++d)
for (int i = 0; i + d < n; ++i) {
final int j = i + d;
for (int m = i; m < j; m += K - 1)
dp[i][j] = Math.min(dp[i][j], dp[i][m] + dp[m + 1][j]);
if (d % (K - 1) == 0)
dp[i][j] += prefix[j + 1] - prefix[i];
}

return dp[0][n - 1];
}
}
``````