Question

1000. Minimum Cost to Merge Stones

中文文档

Description

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

Solutions

Solution 1

class Solution:
  def mergeStones(self, stones: List[int], K: int) -> int:
    n = len(stones)
    if (n - 1) % (K - 1):
      return -1
    s = list(accumulate(stones, initial=0))
    f = [[[inf] * (K + 1) for _ in range(n + 1)] for _ in range(n + 1)]
    for i in range(1, n + 1):
      f[i][i][1] = 0
    for l in range(2, n + 1):
      for i in range(1, n - l + 2):
        j = i + l - 1
        for k in range(1, K + 1):
          for h in range(i, j):
            f[i][j][k] = min(f[i][j][k], f[i][h][1] + f[h + 1][j][k - 1])
        f[i][j][1] = f[i][j][K] + s[j] - s[i - 1]
    return f[1][n][1]

class Solution {
  public int mergeStones(int[] stones, int K) {
    int n = stones.length;
    if ((n - 1) % (K - 1) != 0) {
      return -1;
    }
    int[] s = new int[n + 1];
    for (int i = 1; i <= n; ++i) {
      s[i] = s[i - 1] + stones[i - 1];
    }
    int[][][] f = new int[n + 1][n + 1][K + 1];
    final int inf = 1 << 20;
    for (int[][] g : f) {
      for (int[] e : g) {
        Arrays.fill(e, inf);
      }
    }
    for (int i = 1; i <= n; ++i) {
      f[i][i][1] = 0;
    }
    for (int l = 2; l <= n; ++l) {
      for (int i = 1; i + l - 1 <= n; ++i) {
        int j = i + l - 1;
        for (int k = 1; k <= K; ++k) {
          for (int h = i; h < j; ++h) {
            f[i][j][k] = Math.min(f[i][j][k], f[i][h][1] + f[h + 1][j][k - 1]);
          }
        }
        f[i][j][1] = f[i][j][K] + s[j] - s[i - 1];
      }
    }
    return f[1][n][1];
  }
}

class Solution {
public:
  int mergeStones(vector<int>& stones, int K) {
    int n = stones.size();
    if ((n - 1) % (K - 1)) {
      return -1;
    }
    int s[n + 1];
    s[0] = 0;
    for (int i = 1; i <= n; ++i) {
      s[i] = s[i - 1] + stones[i - 1];
    }
    int f[n + 1][n + 1][K + 1];
    memset(f, 0x3f, sizeof(f));
    for (int i = 1; i <= n; ++i) {
      f[i][i][1] = 0;
    }
    for (int l = 2; l <= n; ++l) {
      for (int i = 1; i + l - 1 <= n; ++i) {
        int j = i + l - 1;
        for (int k = 1; k <= K; ++k) {
          for (int h = i; h < j; ++h) {
            f[i][j][k] = min(f[i][j][k], f[i][h][1] + f[h + 1][j][k - 1]);
          }
        }
        f[i][j][1] = f[i][j][K] + s[j] - s[i - 1];
      }
    }
    return f[1][n][1];
  }
};

func mergeStones(stones []int, K int) int {
  n := len(stones)
  if (n-1)%(K-1) != 0 {
    return -1
  }
  s := make([]int, n+1)
  for i, x := range stones {
    s[i+1] = s[i] + x
  }
  f := make([][][]int, n+1)
  for i := range f {
    f[i] = make([][]int, n+1)
    for j := range f[i] {
      f[i][j] = make([]int, K+1)
      for k := range f[i][j] {
        f[i][j][k] = 1 << 20
      }
    }
  }
  for i := 1; i <= n; i++ {
    f[i][i][1] = 0
  }
  for l := 2; l <= n; l++ {
    for i := 1; i <= n-l+1; i++ {
      j := i + l - 1
      for k := 2; k <= K; k++ {
        for h := i; h < j; h++ {
          f[i][j][k] = min(f[i][j][k], f[i][h][k-1]+f[h+1][j][1])
        }
      }
      f[i][j][1] = f[i][j][K] + s[j] - s[i-1]
    }
  }
  return f[1][n][1]
}