関小君刷题记

题目大意：

切棍子的最小成本

有一根长度为 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]]。但是这样做会牵扯出两个问题：

1. 因为cuts数组并不是严格递增的，我们如何保证cuts[leftIndex]一定小于cuts[rightIndex]，也就是说我们如何保证区间的合法性。
2. cuts数组中并不包含棍子首尾两个点，这样我们无法取得递归的初始边界。

解决方案：

1. 排序一下
2. 将首尾两个点加入到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-解题思路分析/