Skip to content

1000. Minimum Cost to Merge Stones 👍

Approach 1: Top-down 3D DP

  • Time: $O(n^3)$
  • Space: $O(Kn^2)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
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];
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
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];

    for (int[][] A : mem)
      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];
  }
}

Approach 2: Bottom-up 3D DP

  • Time: $O(n^3)$
  • Space: $O(Kn^2)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
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];
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
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 = 1_000_000_000;
    // dp[i][j][k] := the minimum 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(B -> Arrays.fill(B, 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)
          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)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
 public:
  int mergeStones(vector<int>& stones, int k) {
    const int n = stones.size();
    if ((n - 1) % (k - 1))
      return -1;

    vector<vector<int>> mem(n, vector<int>(n, kMax));
    vector<int> prefix(n + 1);

    partial_sum(stones.begin(), stones.end(), prefix.begin() + 1);
    const int cost = mergeStones(stones, 0, n - 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].
  int mergeStones(const vector<int>& stones, int i, int j, int k,
                  const vector<int>& prefix, vector<vector<int>>& mem) {
    if (j - i + 1 < k)
      return 0;
    if (mem[i][j] != kMax)
      return mem[i][j];

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

    return mem[i][j];
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
  public int mergeStones(int[] stones, int k) {
    final int n = stones.length;
    if ((n - 1) % (k - 1) != 0)
      return -1;

    int[][] mem = new int[n][n];
    int[] prefix = new int[n + 1];

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

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

    final int cost = mergeStones(stones, 0, n - 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].
  private int mergeStones(final int[] stones, int i, int j, int k, int[] prefix, int[][] mem) {
    if (j - i + 1 < k)
      return 0;
    if (mem[i][j] != kMax)
      return mem[i][j];

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

    return mem[i][j];
  }
}

Approach 4: Bottom-up 2D DP

  • Time: $O(n^3 / K)$
  • Space: $O(n^2)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
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] := the minimum 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(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 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];
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
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 = 1_000_000_000;

    // dp[i][j] := the minimum 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];
  }
}