[Swift Weekly Contest 126]LeetCode1000. 合并石头的最低成本 |

发布时间：2020-12-14 05:03:22 所属栏目：百科来源：网络整理

导读：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

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 = 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 }

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!