题目大意：
切棍子的最小成本
有一根长度为 n 个单位的木棍，棍上从 0 到 n 标记了若干位置。例如，长度为 6 的棍子可以标记如下：
给你一个整数数组 cuts ，其中 cuts[i] 表示你需要将棍子切开的位置。
你可以按顺序完成切割，也可以根据需要更改切割的顺序。
每次切割的成本都是当前要切割的棍子的长度，切棍子的总成本是历次切割成本的总和。对棍子进行切割将会把一根木棍分成两根较小的木棍（这两根木棍的长度和就是切割前木棍的长度）。请参阅第一个示例以获得更直观的解释。
返回切棍子的 最小总成本 。
示例 1：
输入：n = 7, cuts = [1,3,4,5] 输出：16 解释：按 [1, 3, 4, 5] 的顺序切割的情况如下所示：第一次切割长度为 7 的棍子，成本为 7 。第二次切割长度为 6 的棍子（即第一次切割得到的第二根棍子），第三次切割为长度 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 数组中的所有整数都 互不相同
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1547
解题思路分析：
本题由于切割的顺序会影响到最终的成本，因此我们需要寻找到一个最优解。而先切割哪一个最优我们无法一眼看出，只能遍历所有方式然后比较得出最优方案。这就是动态规划找最优解的思想。对于DP类题目，我比较倾向使用递归加记忆数组的方式来解题，本题也不例外。
解题时，我们定义一个递归函数fun(left, right)，返回值代表分割区间[left, right]需要的最少成本。递归中，我们尝试用cuts数组中的每一个切割点cuts[i]进行分割（注意cuts[i]要在当前left和right之间），本次的切割成本为当前棍子的长度。分割后，棍子变成两个部分，我们将这两部分分别作为两个子问题交给自递归函数去求解。两个子问题的返回值再加上当前的分割成本即是首先切割cuts[i]的最小成本。我们使用该成本更新本层递归函数中的成本最小值。循环完所有切割点后，成本最小值即是本层递归的返回结果。这里用代码简单总结下这部分逻辑：
int help(left, right){ // 递归函数
int min; // 最小成本
for(int i=0;i<cuts.length;i++){ // 循环每一个切割点
if(cuts[i]>=left && cuts[i]<=right){ // 保证当前切割点在当前区间内
// 分割后的两个部分分别交个子问题求最小成本
// cost为先切割cuts[i]后的最优成本
int cost=help(left, cuts[i]) + help(cuts[i], right);
// 用当前cost更新最优cost（循环的目的是为了比较先切割哪个点的总成本最少）
min=Math.min(min, cost);
}
}
min+=(right-left); // 最小成本加上当前切割cuts[i]的成本（区间长度）
return min;
}有了核心的递归逻辑之后，我们再加上一个记忆数组变会大功告成。但是我们发现，递归函数中的两个变量left和right，他们分别代表区间的左右边界，而区间的取值范围在10^6次方，也就是说，如果我们建立一个二维数组，每一个维度的空间都要占用10^6个空间，两个维度总共要占用10^12个空间，这样做即使不会TLE，也会出现内存不足的问题。然而解决这个问题并不难，其实记忆数组保存的是递归函数的结果，而递归函数的参数是一个区间范围，该范围的取值实际上并没有那么多种可能性，因为所有被分割的区间实际上都是通过cuts数组中的分割点得到的，而cuts数组的个数最多不会超过100，也就是说left与right的取值最多分别只有100种而已。
因此我们可以将递归函数改造为fun(leftIndex, rightIndex)。两个参数分别代表cuts数组的下标，也就是说当前棍子的区间为[cuts[leftIndex], cuts[rightIndex]]。但是这样做会牵扯出两个问题：
- 因为cuts数组并不是严格递增的，我们如何保证cuts[leftIndex]一定小于cuts[rightIndex]，也就是说我们如何保证区间的合法性。
- cuts数组中并不包含棍子首尾两个点，这样我们无法取得递归的初始边界。
解决方案：
- 排序一下
- 将首尾两个点加入到cuts中
其他细节请参照代码注释。
实现代码：
int[][] memo; // 记忆数组
public int minCost(int n, int[] cuts) {
Arrays.sort(cuts); // 排序数组
// 初始化记忆数组
memo=new int[cuts.length+2][cuts.length+2];
// 新建一个数组，将棍子的首位和末位加入到cuts数组
int[] c=new int[cuts.length+2];
c[0]=0;
c[c.length-1]=n;
for(int i=1;i<=cuts.length;i++){
c[i]=cuts[i-1];
}
// 递归求解
return help(0,c.length-1,c);
}
// leftIndex：区间左边界在cuts中对应的下标
// rightIndex：区间左边界在cuts中对应的下标
// cuts：所有的切割点
// 返回值：切割区间内所有点的最小成本
int help(int leftIndex, int rightIndex, int[] cuts){
// 如果记忆数组中存在当前解，直接返回
if(memo[leftIndex][rightIndex]>0)return memo[leftIndex][rightIndex];
int l=cuts[leftIndex]; // 区间左边界位置
int r=cuts[rightIndex]; // 区间右边界位置
if(r-l<=1) return 0; // 如果区间长度小于等于1（无法分割），返回0。
int min=Integer.MAX_VALUE; // 成本最小值
// 循环区间内每个切割点
// 注意区间内首尾两个点不需要切割（切了等于没切）
for(int i=leftIndex+1;i<rightIndex;i++){
// 以当前点切割后分成的两个部分，分别交给子方法求最优解，
// 其和为首先进行当前切割后的最小成本
int cost=help(leftIndex,i,cuts)+help(i,rightIndex,cuts);
// 用该成本更新最小成本
min=Math.min(min, cost);
}
// 区间内没有切割点，返回0。
if(min==Integer.MAX_VALUE) min=0;
// 最小成本加上当前切割的成本（当前区间长度）
else min+=(r-l);
// 将最优解存入记忆数组
memo[leftIndex][rightIndex]=min;
return min;
}本题解法执行时间为20ms。
Runtime: 20 ms, faster than 50.00% of Java online submissions for Minimum Cost to Cut a Stick.
Memory Usage: 39.3 MB, less than 50.00% of Java online submissions for Minimum Cost to Cut a Stick.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1547-minimum-cost-to-cut-a-stick-解题思路分析/
《LEETCODE 1547. Minimum Cost to Cut a Stick 解题思路分析》有2条回应