【C 动态规划】1547. 切棒的最低成本
2025-06-24 12:33:55
来源：新华网
本文涉及知识点。
C++动态规划。
Leetcode1547. 切棒的最低成本。
有一个长度 n 单位木棍，棍上从 0 到 n 标记了几个位置。例如，长度为 6 以下的棍子可以标记a;
给你一个整数数组 cuts ，其中 cuts[i] 这意味着你需要把棍子切开。
您可以按顺序完成切割，切割顺序也可以根据需要改变。
每次切割的成本是目前要切割的棍子的长度，切棒的总成本是以往切割成本的总和。切割棍子会把一根棍子分成两根小棍子（这两根木棍的长度和切割前木棍的长度）。请参考第一个例子，以获得更直观的解释。
返回切棒 最小总成本 。
示例 1：
输入：n = 7, cuts = [1，3，4，5]。
输出：16。
说明：按 [1, 3, 4, 5] 如下所示：
第一次切割长度为 7 棍子，成本为 7 。第二次切割长度为 6 #xff08的棍子;也就是说，第一次切割的第二根棍子），第三次切割是长度 4 棍子，最后的切割长度是 3 的棍子。总成本为 7 + 6 + 4 + 3 = 20 。
重新排列切割顺序 [3, 5, 1, 4] 后，总成本 = 16（如示例图中 7 + 4 + 3 + 2 = 16）。
示例 2：
输入：n = 9, cuts = [5，6，1，4，2]。
输出：22。
解释：若按给定顺序切割，则总成本为 25 。总成本 <= 25 有许多切割顺序，例如，[4, 6, 5, 2, 1] 的总成本 = 22，在所有可能的方案中，成本最低。
提示：
2 <= n <= 10。6。
1 <= cuts.length <= min(n - 1, 100)。
1 <= cuts[i] <= n - 1。
cuts 数组中的所有整数都是 互不相同。
动态规划。
将0和n添加到cuts中c;并排序。m = cuts.size。
动态规划的状态表示。
dp[i][j] 切割端点分别为costss[i],costs[j]木棍，切割成本最低。空间的复杂性。：O(mm)。
动态计划的填写顺序。
len = j-i。
len = 2 to m。
转移方程的动态规划。
for(int k = i+1; k < j ;i++)。
MinSelf(dp[i][j] ,cost[j]-cost[i]+dp[i][k]+dp[i][j])。
单个状态转移时间的复杂性a;O(m)，总。时间复杂。：O(mmm)。
动态规划的初始化。
dp[i][i+1] = 0，其它全部是 INT_MAX/2。
动态规划的返回值。
dp[0].back()。
代码。
核心代码。
class。Solution。{ 。5。,6。,1。,4。,2。}。;auto。res。 =Solution。(。)。.。minCost。(。n。,cuts。)。;AssertEx。(。22。,res。)。;}。扩展阅读。
| 我想对你说些什么。 |
|---|
| 工作中遇到的问题，您可以查阅类别中的算法文章，请单击算法和数据汇总。 |
| 学习算法：按章节学习《喜缺全书算法册》，大量问题和测试用例，打包下载。重视操作。 |
| 有效学习：明确的目标 及时的反馈 拉伸区域适当的难度） 专注。 |
| 闻到缺陷，喜(喜)是一个美好的愿望，早期发现问题早期修改问题为老板省钱。 |
| 子墨子言：事无终点无务多业。也就是说，我们常说专业人士做专业的事情。 |
| 如果程序是一条龙，算法是他的眼睛。 |
| 失败+反思=成功 成功+反思=成功。 |
视频课程。
先学简单课程，请移动CSDN学院，听白银讲师（也就是说，鄙人的讲解。
https://edu.csdn.net/course/detail/38771。
如何快速形成战斗？c;分担老板的烦恼，请学习C#入职培训，C++入职培训等课程。
https://edu.csdn.net/lecturer/6176。
测试环境。
操作系统：win7 开发环境 VS2019。 C++17。
或者 操作系统：win10 开发环境： VS2022。 C++17。
如果没有特别说明本。算法。用**C++**实现。
