1000. Minimum Cost to Merge Stones LeetCode Solution

In this guide, you will get 1000. Minimum Cost to Merge Stones LeetCode Solution with the best time and space complexity. The solution to Minimum Cost to Merge Stones problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Minimum Cost to Merge Stones solution in C++
Minimum Cost to Merge Stones solution in Java
Minimum Cost to Merge Stones solution in Python
Additional Resources

1000. Minimum Cost to Merge Stones LeetCode Solution image

Problem Statement of Minimum Cost to Merge Stones

There are n piles of stones arranged in a row. The ith pile has stones[i] stones.
A move consists of merging exactly k consecutive piles into one pile, and the cost of this move is equal to the total number of stones in these k piles.
Return the minimum cost to merge all piles of stones into one pile. If it is impossible, return -1.

Example 1:

Input: stones = [3,2,4,1], k = 2
Output: 20
Explanation: We start with [3, 2, 4, 1].
We merge [3, 2] for a cost of 5, and we are left with [5, 4, 1].
We merge [4, 1] for a cost of 5, and we are left with [5, 5].
We merge [5, 5] for a cost of 10, and we are left with [10].
The total cost was 20, and this is the minimum possible.

Example 2:

Input: stones = [3,2,4,1], k = 3
Output: -1
Explanation: After any merge operation, there are 2 piles left, and we can’t merge anymore. So the task is impossible.

Example 3:

Input: stones = [3,5,1,2,6], k = 3
Output: 25
Explanation: We start with [3, 5, 1, 2, 6].
We merge [5, 1, 2] for a cost of 8, and we are left with [3, 8, 6].
We merge [3, 8, 6] for a cost of 17, and we are left with [17].
The total cost was 25, and this is the minimum possible.

Constraints:

n == stones.length
1 <= n <= 30
1 <= stones[i] <= 100
2 <= k <= 30

Complexity Analysis

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

1000. Minimum Cost to Merge Stones LeetCode Solution in C++

class Solution {
 public:
  int mergeStones(vector<int>& stones, int K) {
    const int n = stones.size();
    vector<vector<vector<int>>> mem(
        n, vector<vector<int>>(n, vector<int>(K + 1, kMax)));
    vector<int> prefix(n + 1);
    partial_sum(stones.begin(), stones.end(), prefix.begin() + 1);
    const int cost = mergeStones(stones, 0, n - 1, 1, K, prefix, mem);
    return cost == kMax ? -1 : cost;
  }

 private:
  static constexpr int kMax = 1'000'000'000;

  // Returns the minimum cost to merge stones[i..j] into k piles.
  int mergeStones(const vector<int>& stones, int i, int j, int k, int K,
                  const vector<int>& prefix, vector<vector<vector<int>>>& mem) {
    if ((j - i + 1 - k) % (K - 1))
      return kMax;
    if (i == j)
      return k == 1 ? 0 : kMax;
    if (mem[i][j][k] != kMax)
      return mem[i][j][k];
    if (k == 1)
      return mem[i][j][k] = mergeStones(stones, i, j, K, K, prefix, mem) +
                            prefix[j + 1] - prefix[i];

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

    return mem[i][j][k];
  }
};
/* code provided by PROGIEZ */

1000. Minimum Cost to Merge Stones LeetCode Solution in Java

class Solution {
  public int mergeStones(int[] stones, int K) {
    final int n = stones.length;
    int[][][] mem = new int[n][n][K + 1];
    int[] prefix = new int[n + 1];

    Arrays.stream(mem).forEach(A -> Arrays.stream(A).forEach(B -> Arrays.fill(B, kMax)));

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

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

  private static final int kMax = 1_000_000_000;

  // Returns the minimum cost to merge stones[i..j] into k piles.
  private int mergeStones(final int[] stones, int i, int j, int k, int K, int[] prefix,
                          int[][][] mem) {
    if ((j - i + 1 - k) % (K - 1) != 0)
      return kMax;
    if (i == j)
      return k == 1 ? 0 : kMax;
    if (mem[i][j][k] != kMax)
      return mem[i][j][k];
    if (k == 1)
      return mem[i][j][k] =
                 mergeStones(stones, i, j, K, K, prefix, mem) + prefix[j + 1] - prefix[i];

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

    return mem[i][j][k];
  }
}
// code provided by PROGIEZ

1000. Minimum Cost to Merge Stones LeetCode Solution in Python

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 = 1'000'000'000;
    // dp[i][j][k] := the minimum 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(stones.begin(), stones.end(), prefix.begin() + 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)
          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];
  }
};
 # code by PROGIEZ