大佬教程收集整理的这篇文章主要介绍了[Swift Weekly Contest 126]LeetCode1000. 合并石头的最低成本 | Minimum Cost to Merge Stones，大佬教程大佬觉得挺不错的，现在分享给大家，也给大家做个参考。
There are N piles of stones arranged in a row. The i-th pile has stones[i] stones.
A @H_295_27@move consists of merging exactly K consecutive piles into one pile,and the cost of this move is equal to the @R_952_10586@l number of stones in these K piles.
Find the minimum cost to merge all piles of stones into one pile. If it is impossible,return -1.
Example 1:
Input: stones = @H_489_42@[3,2,4,1],K = 2 Output: 20 Explanation: We start with [3,1]. We merge [3,2] for a cost of 5,and we are left with [5,1]. We merge [4,1] for a cost of 5,5]. We merge [5,5] for a cost of 10,and we are left with [10]. The @R_952_10586@l cost was 20,and this is the minimum possible.
Example 2:
Input: stones = [3,K = 3 Output: -1 Explanation: After any merge operation,there are 2 piles left,and we can‘t merge anymore. So the task is impossible.
Example 3:
Input: stones = [3,5,1,6],K = 3 Output: 25 Explanation: We start with [3,6]. We merge [5,2] for a cost of 8,and we are left with [3,8,6]. We merge [3,6] for a cost of 17,and we are left with [17]. The @R_952_10586@l cost was 25,and this is the minimum possible.
Note:
有 N 堆石头排成一排，第 i 堆中有 stones[i] 块石头。
每次移动（move）需要将连续的 K 堆石头合并为一堆，而这个移动的成本为这 K 堆石头的总数。
找出把所有石头合并成一堆的最低成本。如果不可能，返回 -1 。
示例 1：
输入：stones = [3,K = 2 输出：20 解释： 从 [3,1] 开始。 合并 [3,2]，成本为 5，剩下 [5,1]。 合并 [4,1]，成本为 5，剩下 [5,5]。 合并 [5,5]，成本为 10，剩下 [10]。 总成本 20，这是可能的最小值。
示例 2：
输入：stones = [3,K = 3 输出：-1 解释：任何合并操作后，都会剩下 2 堆，我们无法再进行合并。所以这项任务是不可能完成的。.
示例 3：
输入：stones = [3,K = 3 输出：25 解释： 从 [3,6] 开始。 合并 [5,2]，成本为 8，剩下 [3,6]。 合并 [3,6]，成本为 17，剩下 [17]。 总成本 25，这是可能的最小值。
提示：
1 class Solution { 2 func mergeStones(_ stones: [Int],_ K: int) -> Int { 3 var n:Int = stones.count 4 var pre:[Int] = [Int](repeaTing:0,count:n + 1) 5 for i in 1...n 6 { 7 pre[i] = pre[i - 1] + stones[i - 1] 8 } 9 var inf:Int = 1000000000 10 var dp:[[[Int]]] = [[[Int]]](repeaTing:[[Int]](repeaTing:[Int](repeaTing:inf,count:205),count:205) 11 for i in 1...n 12 { 13 dp[i][i][1] = 0 14 } 15 for len in 1...n 16 { 17 var i:Int = 1 18 while(i + len - 1 <= n) 19 { 20 var j:Int = i + len - 1 21 if len >= 2 22 { 23 for k in 2...len 24 { 25 var t:Int = i 26 while(t + 1 <= j) 27 { 28 dp[i][j][k] = min(dp[i][j][k],dp[i][t][k - 1] + dp[t + 1][j][1]) 29 t += 1 30 } 31 } 32 } 33 dp[i][j][1] = min(dp[i][j][1],dp[i][j][K] + pre[j] - pre[i - 1]) 34 i += 1 35 } 36 } 37 if dp[1][n][1] >= inf 38 { 39 return -1 40 } 41 return dp[1][n][1] 42 } 43 }
以上是大佬教程为你收集整理的[Swift Weekly Contest 126]LeetCode1000. 合并石头的最低成本 | Minimum Cost to Merge Stones全部内容，希望文章能够帮你解决[Swift Weekly Contest 126]LeetCode1000. 合并石头的最低成本 | Minimum Cost to Merge Stones所遇到的程序开发问题。
如果觉得大佬教程网站内容还不错，欢迎将大佬教程推荐给程序员好友。
本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。