[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 move consists of merging exactly K consecutive piles into one pile, and the cost of this move is equal to the tota

There are N piles of stones arranged in a row.  The i-th pile has stones[i] stones.

A move consists of merging exactly K consecutive piles into one pile,and the cost of this move is equal to the total 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 = [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 total 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 total cost was 25,and this is the minimum possible. 

Note:

1 <= stones.length <= 30 2 <= K <= 30 1 <= stones[i] <= 100

有 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 <= stones.length <= 30 2 <= K <= 30 1 <= stones[i] <= 100 Runtime: 380 ms Memory Usage: 19.3 MB

 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 = 100000000010         var dp:[[[Int]]] = [[[Int]]](repeating:[[Int]](repeating:[Int](repeating:inf,count:205),count:205)11         for i in 1...n12         {13             dp[i][i][1] = 014         }15         for len in 1...n16         {17             var i:Int = 118             while(i + len - 1 <= n)19             {20                 var j:Int = i + len - 121                 if len >= 222                 {23                     for k in 2...len24                     {25                         var t:Int = i26                         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 += 130                         }31                     }32                 }                33                 dp[i][j][1] = min(dp[i][j][1],dp[i][j][K] + pre[j] - pre[i - 1])                34                 i += 135             }36         }37         if dp[1][n][1] >= inf38         {39             return -140         }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所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。