2021-02-25 20:22 已编辑北京化工大学 Java

关注

剑指offer小解析——14_I_剪绳子

文章目录

剑指offer小解析——14_I_剪绳子

剑指offer小解析——14_I_剪绳子

1.题目描述

剑指 Offer 14- I. 剪绳子

难度中等112

给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]...k[m-1] 。请问 k[0]*k[1]*...*k[m-1] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。

示例 1：

输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1

示例 2:

输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36

提示：

2 <= n <= 58

2.动态规划

2.1 正常人的思维

//time: 38.74%
//memory: 77.31%
public static int cuttingRope(int n) {
   
    if (n < 2) {
   
        return 0;
    }
    if (n == 2) {
   
        return 1;
    }
    int[] res = new int[n + 1];
    res[1] = 0;
    res[2] = 1;
    int max = 0;
    for (int i = 3; i <= n; i++) {
   
        for (int j = 1; j <= i / 2; j++) {
   
            int temp = (Math.max(j, res[i]) * Math.max((i - j), res[i - j]));
            if (temp > max) {
   
                max = temp;
            }
        }
        res[i] = max;
    }
    return res[n];
}

这里我们可以想一想曾经做过的斐波那契数列，对于本题来说，我们提供两个初始值，绳长为1（或者为0）时我们返回0，因为1已经是最小单位了，剪不了了；绳长为2时我们返回1，即剪成1米和1米的两段。

如果绳长大于2呢？我们可以设置一个数组来存储每个长度对应的最优结果。我们设这个数组为res，res的下标代表绳子长度，即res[1]代表绳长为1米，res[2]代表绳长为2米……，那么我们初始化res[1] = 0， res[2] = 1。

做完初始化工作后，我们就要开始利用已有的结果计算未知的结果。我们首先写一个循环，从3开始，到绳长为n时结束，这个循环代表了绳子的长度。比如i = 4，说明我们正在计算绳长为4米时候的最优解。

然后我们进行剪绳，本来我们可以剪的长度是从1米到i - 1米，但举个例子来说，2 + 4 = 6，可4 + 2也等于6，这样就重复了，我们只需要剪到中间就行，不需要再往右了。

如果绳长为3米，我们的最优剪法应该是剪成1米和2米，结果为2，我们想当然地使用res[j] * res[i - j] （j就是你剪断的长度，i -j就是剩下的长度）= res[2] * res[1] = ……欸，等等，res[2] = 1，res[1] = 0，这俩乘积是0啊！

这就需要你仔细想一想，无论是res[2]还是res[1]，都是他们作为题目输入的长度时，必须剪绳子获得的最优解，但是如果他们作为计算的中间量的时候，就比如我们输入3，剪断成2和1，你还必须剪那个2米的绳子吗？不需要，因为他是中间量，我们没必要非得剪断他，很明显，2米绳子的本身长度大于他作为输入时的最优解，所以我们选择使用Math.max方法来获得2米绳子的长度及其最优解之间的最大值即可。

然后就简单了，我们定义一个max量，记录乘积的最大值。每次内循环结束这个max值归零或者不归零都行，反正他都是递增的，每次循环都一定会产生一个值把他覆盖掉，无所谓。

但是这个解法，耗时，时间上只能达到38%，还不够好，问题出在哪里呢？

2.2 很多人都会写但没多少人证明过的一种方式

public int cuttingRope(int n) {
   
    if (n < 2) {
   
        return 0;
    }

    if (n == 2) {
   
        return 1;
    }

    if (n == 3) {
   
        return 2;
    }

    int[] res = new int[n + 1];
    res[1] = 0;
    res[2] = 2;
    res[3] = 3;
    int max = 0;
    for (int i = 4; i <= n; i++) {
   
        for (int j = 1; j <= i / 2; j++) {
   
            int temp = res[j] * res[i - j];
            if (temp > max) {
   
                max = temp;
            }
        }
        res[i] = max;
    }
    return res[n];
}

我们先带着上面的疑问，看完上面的代码，觉得这个跟之前的思路也差不多，稍微看看好像能看懂，但是，又总觉得哪里不对劲？

为什么是4，我的循环为什么要从4开始？不是从5或者6或者100？res[2]是啥？res数组不应该记录的最优解吗？如果res[2]代表的是2米长的绳子的最优解，不应该是1吗？咋res[1]、res[2]、res[3]的值都等于他们自身的长度了？

这个问题的核心原因，也是2.1小节耗时过多的原因——判断一段绳子的最优解是否比它的本身长？

换个说法，比如我有一个3米长的绳子，如果他作为题目本身，让你剪一个3米长的绳子，你知道最优解是1* 2 = 2；但是如果我的绳子长4米呢？当你把绳子剪成3米和1米的时候，你还会继续剪那个3米长的绳子吗？你不会，因为如果继续剪3米的那段，你就把3 * 1 = 3变成了1 * 2 * 1 = 2，反而减小了。所以如果剪断的过程中出现3米的子绳段，我们选择不剪，直接保留，因为他的最优解小于他本身的长度。这也是为什么我们在2.1小节，每次都要使用Math.max方法。

但是，我们真的每次都需要Math.max吗？比如4，我们知道他的最优解是剪成2 、 2的两段，结果是4，等于绳长；5可以分成2和3，结果是6，比5还大；6可以分成2和4，结果是8；7可以分成3和4，结果是12……wait a minute，好像，从4开始，他们的最优解都大于或者等于绳子的长度。那么我们是否可以这样，如果输入的n是0到3，我们直接返回最优解；但是如果n大于3，那么我们设作为子段的0、1、2、3的**“最优解”**分别都是他们自身的长度。然后每次循环计算的时候我们就可以直接使用int temp = res[j] * res[i - j];了，这样岂不妙哉？

But，你这么做的前提是啥？前提是知道上面的猜想从4开始，他们的最优解都大于或者等于绳子的长度是正确的，接下来就是证明。

（警告🔥，以下涉及数学知识，而且我高数已经快忘完了，写的跟喝醉了似的，你看不懂不要怀疑自己，绝对是我写的不够清楚明白）

首先我们假设一个数字n( $\in Z_{}^{+}$ )，并且设他的一个加数为x，我们要找到一个最小值，从这个值开始，所有的数一定存在一组加数，使得这两个加数的成绩大于等于这个数本身。用符号描述就是
$\forall m \in Z_{}^{+}, 如果m \geq n(n \in Z_{}^+),则\exists x < m,使得(m - x)\times x \geq m。求n。$
那么我们需要利用 $x)\times x \geq n$ 来求得n的最小值（很明显x一定是大于1的，也就是x≥2，因为如果x=1，结果只能是n-1，不可能等于或者大于n的）

通过化简，我们获得了 $\frac{x^{2}}{x - 1} \leq n (x \geq 2)$ ，我们现在只需要求得 $\frac{x^{2}}{x - 1}$ 的最小值。

对 $\frac{x^{2}}{x - 1}$ 进行变形，获得 $\frac{(x - 1)^2 + 2x - 1}{x - 1}$ ，即 $\frac{2x - 1}{x - 1}$

继续变形化简，获得 $\frac{1}{x - 1}$

求导获得 $\frac{1}{(x - 1)^2} = \frac{x(x-2)}{(x-1)^2}(x\geq 2)$

很明显，在x≥2的区间范围内， $\frac{x^{2}}{x - 1}$ 的导数始终大于等于0，即它始终是增函数，最小值即为x=2时。我们带入得到4，也就是说，从4开始，n一定存在两个加数的乘积大于等于n。那么放到我们的题目就是从，每个子段，只要他的长度大于4，他的最优解一定大于他自身的长度。

上面如果我讲的还不够清楚，没关系，你只需要知道我们的思路应该是这样

如果绳子的长度为0、1、2、3，你就直接返回对应的最优解即可，即0、0、1、2；
如果绳子的长度大于等于4，我们定义res数组，注意，res的下标就是绳子的长度。那么现在res[1]，res[2]，res[3]代表的是长度为1、2、3的**子段（注意，他们是作为子段，就是过程中被剪出来的绳子）**能提供的最大长度，我们分别设为他们各自的长度（通过上面的证明我们已经知道，只有大于4的线段才会出现加数乘积大于本身的情况，所以1、2、3这些段如果是作为中间量出现的话，就没必要继续剪下去了）。

别的我就不多说了，只要理解了上面的，这个代码本身没有难度，10分钟就能完整地背下来。

3.贪婪算法

在说这个算法之前，我们可以看看如果我们输入n = 10，利用上面的动态规划算***怎么运行

运行到10，可以分成2和8，8又可以分成2和6，6又可以分成3和3，最后的结果也就是2 * 2 * 3 * 3 = 36

我们发现了，在剪绳子宇宙的尽头是铁岭……不对，

我们发现，宇宙的尽头是2和3，你无论是什么数我最后都能给你分成2和3，而且当n ≥5的时候，你证明一下，

3(n - 3) ≥ 2(n - 2)

这说明当n ≥5的时候，应该尽量剪出来3米的绳子。而当长度为4的时候，2 * 2 > 1 * 3，这时候我们就要收手，要剪出来两段2米的。

那么我们用n / 3 获得可以分成的3米的数量numberOf3，这时候余数可能为1或者2，如果余数是1，我们就让numberOf3-1，拿出一个3米的子段跟1米合并，成为1个4米的子段，这样效果更好。

如果余数是2，那就让它2着，不用管

然后我们通过(n - numberOf3 * 3) / 2来获得2米子段是数量numberOf2，最后利用Math.pow(3, numberOf3)*Math.pow(2, numberOf2)来获得结果。

public int cuttingRope(int n) {
   
    if (n < 2) {
   
        return 0;
    }
    if (n == 2) {
   
        return 1;
    }

    if (n == 3) {
   
        return 2;
    }

    int numberOf3 = n / 3;
    if (n - 3 * numberOf3 == 1) {
   
        numberOf3--;
    }
    int numberOf2 = (n - numberOf3 * 3) / 2;
    return (int)(Math.pow(3, numberOf3) * Math.pow(2, numberOf2));
}