剑指offer16割绳子

题目

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

输入描述

输入一个数 n，意义见题面。（2 <= n <= 60）

输出描述:

输出答案。

解题思路

1 动态规划

• 条件一：求一个问题的最优解
• 条件二：该问题能够分解成若干个子问题，并且子问题也存在最优解
• 条件三：子问题之间还有重叠的更小的子问题

2 本题思路

• 求剪出绳子长度的乘积的最大值，这个符合第一个条件
• 我们将乘积以函数表示，即 f(n)。假设第一刀减在长度为 i(0<i<n)的位置，于是把绳子剪成了长度分别为 i 和 n - i 两段。想要得到整个问题的最优解 f(n), 就需要同样用最优化的方法把长度为 i 和 n - i 的两段分别剪成若干段，使得它们剪出的每段绳子的长度成绩最大。这符合第二个条件。
• 大问题分解为小问题时，会出现相互重叠的更小的子问题。如，绳子长为 10，首先将其分为 4 和 6。长度为 4 的一段，可以分为 2 和 2；长度为 6 的可以分为 2 和 4。可以发现，f(2)是 f(4)和 f(6)公共的更小的子问题。

所以，这里采取的方法是自下而上的方法。先从小问题开始计算，并把已经解决的子问题的 最优解存储 下来（通常的做法是存储在一位数组或者二维数组中），并把子问题的最优解组合起来逐步解决大的问题。

3 测试用例

• 功能测试用例：绳子的长度大于 5
• 边界测试用例：绳子的长度分别为 0,1,2,3,4

    /**
     * 使用动态规划的方法
     * @param length
     * @return
     */
    public static int getMaxResult(int length) {
        // 如果 length 小于等于 3，则直接输出结果
        if (length < 2)
            return 1;
        if (length ==2)
            return 1;
        if (length == 3)
            return 2;

        // 如果 length 大于 3，则又有新的内容
        int[] results = new int[length + 1];
        // 这里说明下，现在 length 大于 4，那么当子问题分别为 0,1,2,3 时，我们直接不分不切割，此时就是子问题对应的最优解
        results[0] = 0;
        results[1] = 1;
        results[2] = 2;
        results[3] = 3;

        int max = 0;
        for (int i = 4; i <= length; i++) {max = 0;// 每次都有重置最大值，因为有可能上次求出的分段内容最大值大于 f(j)*f(j-1)的值，最终得到的很有可能是上次的最大值
            for (int j = 1; j <= i / 2; ++j) {int result = results[j] * results[i-j];
                if (max < result) {max = result;}
                results[i] = max;
            }
        }
        max = results[length];
        return max;
    }

4 尝试贪婪算法

分为下面几种情况：

• n<2, 返回 0
• n==2, 最大乘积为 1
• n==3, 最大乘积为 2
• n==4, 最大乘积为 2 *2=4
• n>=5, 需要进行以下说明

当 n >= 5 时，我们可以分别切割为 1 (n-1)、2(n-2)、3(n-3)、4(n-4)、5*(n-5)
得到的时 3 (n-3)得到的结果最大，紧跟着的是 2 (n-2)。所以应该尽可能多的将绳子切割为 3。
此时，会出现剩余为 1 或 2 两种情况。如果为 1 的话，我们需要将剩余的长度修改为 4，因为 4 (n-4)>1(n-1)；如果剩余为 2 的话，没有办法再切割了。

所以，其中算法的思路是：

• 向下取整，求 3 的倍数
• 如果剩余的长度为 1，可将 3 的倍数减一(使剩余的内容为 4)
• (总长度 -3* 3 的倍数)/2 的到 2 的倍数
• 最终的结果是 pow(3,3 的倍数)*pow(2,2 的倍数)

    /**
     * 使用贪婪算法
     * @param length
     * @return
     */
    public static int getMaxResult2(int length) {
        // 如果 length 小于等于 3，则直接输出结果
        if (length < 2)
            return 1;
        if (length ==2)
            return 1;
        if (length == 3)
            return 2;
        // 求出可以切割成 3 的个数
        int timesof3 = length / 3;
        // 当以 3 为单位来切割时，如果最后一段的长度为 4，需求将最后一段按照 2 + 2 来切割
        if (length - timesof3 * 3 == 1) {timesof3--;}

        // 求出可以剩余可以切割为 2 的个数
        int timesof2 = (length - timesof3 * 3) / 2;

        return (int)(pow(3, timesof3)) * (int)(pow(2, timesof2));
    }

本题 github 地址，欢迎 star
https://github.com/justn0w/algorithm/tree/master/offer_16