寻找在 Python 中合并石头的最低成本的程序
假设我们有N堆石头排成一排。这里第i堆有石头[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，这是最低成本。
示例
让我们看下面的实现来更好地理解
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