C++刷leetcode（1547. 切棍子的最小成本）【动态规划】

糖逗

题目描述：

1. 有一根长度为 n 个单位的木棍，棍上从 0 到 n 标记了若干位置。例如，长度为 6 的棍子可以标记如下：
   
2. 
   
3. 
   
4. 
   
5. 给你一个整数数组 cuts ，其中 cuts[i] 表示你需要将棍子切开的位置。
   
6. 
   
7. 你可以按顺序完成切割，也可以根据需要更改切割的顺序。
   
8. 
   
9. 每次切割的成本都是当前要切割的棍子的长度，切棍子的总成本是历次切割成本的总和。对棍子进行切割将会把一根木棍分成两根较小的木棍（这两根木棍的长度和就是切割前木棍的长度）。请参阅第一个示例以获得更直观的解释。
   
10. 
    
11. 返回切棍子的 最小总成本 。
    
12. 
    
13.  
    
14. 
    
15. 示例 1：
    
16. 
    
17. 
    
18. 
    
19. 输入：n = 7, cuts = [1,3,4,5]
    
20. 输出：16
    
21. 解释：按 [1, 3, 4, 5] 的顺序切割的情况如下所示：
    
22. 
    
23. 第一次切割长度为 7 的棍子，成本为 7 。第二次切割长度为 6 的棍子（即第一次切割得到的第二根棍子），第三次切割为长度 4 的棍子，最后切割长度为 3 的棍子。总成本为 7 + 6 + 4 + 3 = 20 。
    
24. 而将切割顺序重新排列为 [3, 5, 1, 4] 后，总成本 = 16（如示例图中 7 + 4 + 3 + 2 = 16）。
    
25. 示例 2：
    
26. 
    
27. 输入：n = 9, cuts = [5,6,1,4,2]
    
28. 输出：22
    
29. 解释：如果按给定的顺序切割，则总成本为 25 。总成本 <= 25 的切割顺序很多，例如，[4, 6, 5, 2, 1] 的总成本 = 22，是所有可能方案中成本最小的。
    
30. &#160;
    
31. 
    
32. 提示：
    
33. 
    
34. 2 <= n <= 10^6
    
35. 1 <= cuts.length <= min(n - 1, 100)
    
36. 1 <= cuts[i] <= n - 1
    
37. cuts 数组中的所有整数都 互不相同
    
38. 
    
39. 来源：力扣（LeetCode）
    
40. 链接：https://leetcode-cn.com/problems/minimum-cost-to-cut-a-stick
    
41. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

1. class Solution {
   
2. public:
   
3.     int minCost(int n, vector<int>& cuts) {
   
4.         int len = cuts.size();
   
5.         sort(cuts.begin(), cuts.end());
   
6.         cuts.insert(cuts.begin(), 0);
   
7.         cuts.push_back(n);
   
8.         vector<vector<int> >dp(len + 2, vector<int>(len + 2));
   
9.         for(int i = len; i >= 1; i--){
   
10.             for(int j = i; j <= len; j++){
    
11.                 dp[i][j] = (i == j ? 0 : INT_MAX);
    
12.                 for(int k = i; k <= j; k++){
    
13.                     dp[i][j] = min(dp[i][j], dp[i][k-1] + dp[k+1][j]);
    
14.                 }
    
15.                 dp[i][j] += cuts[j+1] - cuts[i-1];
    
16.             }
    
17.         }
    
18.         return dp[1][len];
    
19.     }
    
20. };

复制代码

参考链接：https://leetcode-cn.com/problems ... -by-leetcode-solut/

糖逗