数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法学研究Python程序：查找合并石头的最小成本
假设我们有N堆石头排成一排。这里第i堆有stones[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)的数组，并填充0
对于i从1到n，执行
sums[i] := sums[i-1]+nums[i-1]
对于length从K到n，执行
对于i从0到n-length，执行
j := i+length-1
dp[i, j] := 无穷大
对于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
更新于：2021年10月7日
227次浏览
广告