X

LEETCODE 1547. Minimum Cost to Cut a Stick 解题思路分析

题目大意:

切棍子的最小成本

有一根长度为 n 个单位的木棍,棍上从 0n 标记了若干位置。例如,长度为 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-解题思路分析/
Categories: leetcode
kwantong:

View Comments (2)