面试题14：剪绳子

2018-11-14 本文已影响0人修司敦

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

解析：该题可以用动态规划的思路解，也可以用贪心算法的思路解。
动态规划的话，首先看满不满足这两个经典的条件：大问题可以分解为若干个小的子问题，而且子问题需要大量的重复计算。这两个条件在这里都是满足的：例如绳子的长度是 12 的时候，一刀切下去变成 2 和 10，10 就成了一个子问题。10 还需要一刀切下去变成 2 和 8，这样 2 就重复了一次。虽说把 12 切成 2 和 10 不一定是最好的方案，但是我的目的在于证明子问题是有重复情况发生的。这个时候可以把子问题得到的结果提前记录下来，从而尽量避免无意义的重复，写法也就不是函数递归了，能够获得比较好的算法。在确定可以使用动态规划的时候，我们需要明确自己的目的：我们要找到最优的子问题划分。把 12 切成 2 和 10 好呢，还是切成 3 和 9 好呢？显然， $2\times 10 \lt 3\times 9$ ，所以选择 3 和 9 比 2 和 10 要好。但是 3 和 9 就一定是最好的吗？ $3\times 9 \lt 4\times 8$ ，那么 4 和 8 就一定最好吗？你会发现，从上到下的分析，并不容易得到正确答案。那么我们应该换一种思路，从下到上的分析：

假设绳子总共有 2 厘米长，由于必须剪一刀，乘积是 1。
假设绳子总共有 3 厘米长，那么乘积是 2。
假设绳子总共有 4 厘米长，剪成 2 和 2 要比 1 和 3 强，乘积是 4。注意，我们可以只剪一刀，这样子条件已经满足了，剪出来的 3 不需要再剪一刀了，因为再剪一刀反而让乘积变小了。
假设绳子总共有 5 厘米长，剪成 2 和 3 要比 1 和 4 强。同样，剪出来的 3 和 4 不需要再剪一刀了，因为再剪一刀反而让乘积变小了。
假设绳子总共有 6 厘米长，剪成 3 和 3 要比 2 和 4 强。

分析到这里的时候，我们其实已经有一些子问题的结果了。剪出来的绳子片段：

长度为 1 的时候，它最高能贡献的乘积因子是 1；
长度为 2 的时候，它最高能贡献的乘积因子是 2；
长度为 3 的时候，它最高能贡献的乘积因子是 3，因为之前已经剪过一刀了，所以不需要把 3 再剪一次；
长度为 4 的时候，它最高能贡献的乘积因子是 4，这个时候多剪一刀与不剪是没区别的；
长度为 5 的时候，它最高能贡献的乘积因子是 6，如果这个片段不剪的话能贡献 5，剪了的话能贡献 $2\times3=6$ ，当然选择再剪一刀；
长度为 6 的时候，它最高能贡献的乘积因子是 9，不剪的话能贡献 6，剪了的话能贡献 $3\times3=9$ ，当然选择再剪一刀；
……

发现没有，上面的剩余长度为 4 的问题，可以理解成两个剩余长度为 2 的乘积；剩余长度为 5 的问题，可以理解为两个剩余长度为 2 和 3 的乘积；剩余长度为 6 的问题，可以理解为两个剩余长度为 3 的乘积……如果用函数的思想，用 $f(n)$ 代表绳子剩余长度为 n 的时候能够提供的最大贡献，那么 $f(1)=1$ ， $f(2)=2$ ， $f(3)=3$ ， $f(4)=f(2)\times f(2)=4$ ， $f(5)=f(2)\times f(3)=6$ ， $f(6)=f(3)\times f(3)=9$ ……

我们在确定 $f(4)$ 、 $f(5)$ 、 $f(6)$ 的值的时候，是通过比较两个子问题乘积的更大值来得到的。例如在判定 $f(5)$ 的时候， $f(5)=f(2)\times f(3)=6$ ，也可以是 $f(5)=f(1)\times f(4)=4$ ，这两种情况中前者更大，所以选择前者的方案。更一般的，我们考虑 $f(n)=?$ ，我们比较的过程是 $f(n)=f(2)\times f(n-2)=?$ ， $f(n)=f(3)\times f(n-3)=?$ ， $f(n)=f(4)\times f(n-4)=?$ ， $f(n)=f(5)\times f(n-5)=?$ ，……， $f(n)=f(n/2)\times f(n/2)=?$ 这么多结果中最大的那一个。在刚刚的考虑过程中， $f(4)$ 、 $f(5)$ 这些值在之前的计算已经记录了结果，所以我们直接用就好。

分析到这一步了，你是不是已经很清楚动态规划的代码该怎么写了？

// ====================动态规划====================
int maxProductAfterCutting_solution1(int length)
{
    if (length < 2) return 0;
    else if (length == 2) return 1;
    else if (length == 3) return 2;
    else if (length >= 4)
    {
        int product[length+1];
        product[0] = 0; //这个其实写不写都行，后面的代码也用不到这个
        product[1] = 1; //这个也用不到
        product[2] = 2; //这里的 2 指的是剩下了一段长度为 2 的绳子，可以不剪
        product[3] = 3; //这里的 3 指的是剩下了一段长度为 3 的绳子，可以不剪

        int max = 0;
        for (int i=4; i<=length; ++i)
        {
            max = 0;
            for (int j=2; j<=i/2; ++j) //从 2 开始比较
            {
                if (max < product[j]*product[i-j])
                    max = product[j]*product[i-j]; //比较出最大的那个情况
            }
            product[i] = max; //记录下来
        }
        return product[length]; //这个时候从 0 到 n 的最优情况都记录下来了
    }
    return 0;
}

下一个思路是贪心算法。在使用贪心算法的时候，我们同样需要提供一些数学证明，来证明可以用贪心的思路解题。同样的，

假设绳子总共有 2 厘米长，由于必须剪一刀，乘积是 1。
假设绳子总共有 3 厘米长，那么乘积是 2。
假设绳子总共有 4 厘米长，剪成 2 和 2 要比 1 和 3 强，乘积是 4。
假设绳子长度大于 5 厘米，即 $n\geqslant5$ ，我们可以证明 $3(n-3)\geqslant 2(n-2)\gt n,\forall n\geqslant 5$ 。因此切比不切强，而且切成 3 的情况比切成 2 的情况贡献的乘积多，我们应该尽量多切成 3 的片段。

因此，思路就很简单了：如果把绳子尽可能多的切成若干个 3 的片段，剩下来的长度可能是 1、2，如果少切一刀的话，也会剩下 4、5、6。为什么考虑少切一刀的情况呢？我们来看一下：

如果切到最后剩下了长度为 6 的片段，再切出来一段 3，剩余 3，能多乘 9，那就切；
如果切到最后剩下了长度为 5 的片段，再切出来一段3，剩余 2，能多乘 6，那就切；
如果切到最后剩下了长度为 4 的片段，再切出来一段3，剩余 1，能多乘 3；但是如果不切的话，能多乘 4！

那么这个剩余长度是 4 的情况就是特殊情况：如果剩余长度为 4，那么选择不切，而不是切成 1 和 3。到这里，算法就能写出来了：

// ====================贪心算法====================
int maxProductAfterCutting_solution2(int length)
{
    if (length < 2) return 0;
    else if (length == 2) return 1;
    else if (length == 3) return 2;
    else
    {
        int piecesOfThree = length/3;
        //pow 函数的结果是 double 类型，所以使用类型转换：
        int productOfThrees = static_cast<int>(pow(3, piecesOfThree));
        if (length%3==0) return productOfThrees;
        else if (length%3==2) return 2*productOfThrees;
        else return productOfThrees/3*4;
    }
}

面试题14：剪绳子

猜你喜欢

热点阅读