用 Python 编写程序，查找合并石头的最低成本
假设我们有 N 堆石头排成一排。这里第 i 堆有 stone[i] 个石头。移动包括将 K 个连续的堆合并为一个，现在此移动的成本等于这 K 个堆中的石头总数。我们必须找到将所有堆石头合并为一个的最低成本。如果没有这样的解决方案，则返回 -1。
因此，如果输入为 nums = [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，这是最小成本。
要解决这个问题，我们将遵循以下步骤 −
n := nums 的大小
如果 (n-1) mod (K-1) 不为 0，则
返回 -1
dp := 一个 n x n 数组并用 0 填充
sums := 大小为 (n+1) 的 n 数组并用 0 填充
对于范围从 1 到 n 的 i，执行
sums[i] := sums[i-1]+nums[i-1]
对于长度在 K 到 n 范围内的情况，执行
对于 i 在 0 到 n 长度范围内的情况，执行
j := i+length-1
dp[i, j] := infinity
对于 t 在 i 到 j-1 范围内的情况，每一步更新 K-1，执行
dp[i][j] = dp[i, j] 和 (dp[i, t] + dp[t+1, j]) 中的最小值
如果 (j-i) mod (K-1) 等于0，则
dp[i, j] := dp[i, j] + sums[j+1]-sums[i]
返回 dp[0, n-1]
示例
让我们看看下面的实现以便更好地理解
import heapq def solve(nums, K): n = len(nums) if (n-1)%(K-1) != 0: return -1 dp = [[0]*n for _ in range(n)] sums = [0]*(n+1) for i in range(1,n+1): sums[i] = sums[i-1]+nums[i-1] for length in range(K,n+1): for i in range(n-length+1): j = i+length-1 dp[i][j] = float('inf') for t in range(i,j,K-1): dp[i][j] = min(dp[i][j], dp[i][t]+dp[t+1][j]) if (j-i)%(K-1)==0: dp[i][j] += sums[j+1]-sums[i] return dp[0][n-1] nums = [3,2,4,1] K = 2 print(solve(nums, K))输入
[3,2,4,1], 2
输出
20
相关文章
有用资源
python 参考教程 - 该教程包含有关 python 的更多信息:https://www.cainiaomax.com/python/
