返回介绍

solution / 1000-1099 / 1000.Minimum Cost to Merge Stones / README

发布于 2024-06-17 01:03:32 字数 5610 浏览 0 评论 0 收藏 0

1000. 合并石头的最低成本

English Version

题目描述

n 堆石头排成一排,第 i 堆中有 stones[i] 块石头。

每次 移动 需要将 连续的 k 堆石头合并为一堆,而这次移动的成本为这 k 堆中石头的总数。

返回把所有石头合并成一堆的最低成本。如果无法合并成一堆,返回 -1

 

示例 1:

输入:stones = [3,2,4,1], K = 2
输出:20
解释:
从 [3, 2, 4, 1] 开始。
合并 [3, 2],成本为 5,剩下 [5, 4, 1]。
合并 [4, 1],成本为 5,剩下 [5, 5]。
合并 [5, 5],成本为 10,剩下 [10]。
总成本 20,这是可能的最小值。

示例 2:

输入:stones = [3,2,4,1], K = 3
输出:-1
解释:任何合并操作后,都会剩下 2 堆,我们无法再进行合并。所以这项任务是不可能完成的。.

示例 3:

输入:stones = [3,5,1,2,6], K = 3
输出:25
解释:
从 [3, 5, 1, 2, 6] 开始。
合并 [5, 1, 2],成本为 8,剩下 [3, 8, 6]。
合并 [3, 8, 6],成本为 17,剩下 [17]。
总成本 25,这是可能的最小值。

 

提示:

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

解法

方法一:动态规划(区间 DP)+ 前缀和

我们不妨记题目中的 $k$ 为 $K$,石头的堆数为 $n$。

定义 $f[i][j][k]$ 表示将区间 $[i, j]$ 中的石头合并成 $k$ 堆的最小成本。初始时 $f[i][i][1] = 0$,其他位置的值均为 $\infty$。

注意到 $k$ 的取值范围为 $[1, K]$,因此我们需要枚举 $k$ 的值。

对于 $f[i][j][k]$,我们可以枚举 $i \leq h \lt j$,将区间 $[i, j]$ 拆分成两个区间 $[i, h]$ 和 $[h + 1, j]$,然后将 $[i, h]$ 中的石头合并成 $1$ 堆,将 $[h + 1, j]$ 中的石头合并成 $k - 1$ 堆,最后将这两堆石头合并成一堆,这样就可以将区间 $[i, j]$ 中的石头合并成 $k$ 堆。因此,我们可以得到状态转移方程:

$$ f[i][j][k] = \min_{i \leq h < j} {f[i][h][1] + f[h + 1][j][k - 1]} $$

我们将区间 $[i, j]$ 的 $K$ 堆石头合并成一堆,因此 $f[i][j][1] = f[i][j][K] + \sum_{t = i}^j stones[t]$,其中 $\sum_{t = i}^j stones[t]$ 表示区间 $[i, j]$ 中石头的总数。

最后答案即为 $f[1][n][1]$,其中 $n$ 为石头的堆数。

时间复杂度 $O(n^3 \times k)$,空间复杂度 $O(n^2 \times k)$。其中 $n$ 为石头的堆数。

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]
}

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。
列表为空,暂无数据
    我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
    原文