Python中合并石头的最小成本程序
假设有N堆按顺序排列的石头,其中第i堆有 stones[i] 颗石头。将K个相邻的堆合并成一堆,此操作的成本等于这K堆石头中的总数。我们必须找到将所有石头堆合并成一堆的最小成本。如果无法实现此解,返回-1。
因此,如果输入是 nums = [3,2,4,1],K = 2,则输出将是20,因为最初有[3、2、4、1]。然后合并成代价为5的[3、2],我们有[5、4、1]。之后通过代价为5合并[4、1],我们有[5、5]。然后通过代价为10合并[5、5],我们有[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]
- 对于长度在K到n的范围内,执行以下操作:
- 对于 i 在 0 到 n-length 的范围内,执行以下操作:
- j := i+length-1
-
dp[i, j] := 无限大
-
对于每一步平均更新K-1,t在范围 i 到 j-1 中,执行以下操作:
-
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]
- j := i+length-1
- 对于 i 在 0 到 n-length 的范围内,执行以下操作:
-
返回 dp[0, n-1]
示例
看下面的实现以获得更好的理解