《剑指offer第二版》面试题14：剪绳子

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

动态规划的概念

如果面试题是求一个问题的最优解（通常是求最大值或者最小值），而且该问题能够分解成若干个子问题，并且子问题之间还有重叠的更小的子问题，就可以考虑用动态规划来解决这个问题。

我们在应用动态规划之前要分析能否把大问题分解成小问题，分解后的小问题也存在最优解。如果把小问题的最优解组合起来能够得到整个问题的最优解，那么我们可以应用动态规划解决这个问题。

在应用动态规划解决问题的时候，我们总是从解决最小问题开始，并把已经解决的子问题的最优解存储下来，并把子问题的最优解组合起来逐步解决大的问题。

应用动态规划的时候，我们事先是不知道那种方法是最优的解法，只好把所有的可能都尝试一遍。

解题思路：首先定义函数f(n)为把长度为n的绳子剪成若干段后各段长度乘积的最大值。在剪第一刀的时候，我们有n-1中选择，也就是剪出来的第一段绳子的可能长度分别为1,2,3...,n-1。因此f(n) =max(f(i) * f(n-i))，其中0<i<n。

这里注意：f(n) = max(f(i) * f(n-i)) ，fn是所有可能的f(i) * f(n-i)的最大值，其中0<i<n。

这是一个从上至下的递归公式。由于递归会有很多重复的子问题，从而有大量不必要的重复计算。一个更好的办法是按照从下到上的顺序计算，也就是说我们先得到，再得到，，直到得到。

/**
 * 动态规划
 *
 * @param length 绳子的长度
 * @return
 */
public static int maxProduceAfterCutting(int length) {
    //异常情况
    if (length < 2) {
        return 0;
    }
    //绳子剪成m段，m>1 ,所以我们得剪成 1 * 1
    if (length == 2) {
        return 1;
    }
    //长度为3，只能剪成 1*2 最长的一段
    if (length == 3) {
        return 2;
    }
    //上面分别返回了长度小于等于3时候的最优解，下面是计算长度大于3时候的情况
    //注释1处，定义一个数组，用来保存计算出来的子问题的最优解
    int[] products = new int[length + 1];
    products[0] = 0;
    products[1] = 1;
    //注释2处，
    products[2] = 2;
    //注释3处，
    products[3] = 3;
    int result = 0;
    //开始计算
    for (int i = 4; i <= length; i++) {
        int max = 0;
        //注释4处，直接从j=1开始，不需要从0开始。
        for (int j = 1; j <= i / 2; j++) {
            int product = products[j] * products[i - j];
            if (max < product) {
                max = product;
            }
        }
        products[i] = max;
    }
    result = products[length];
    return result;
}

注释1处，定义一个数组，用来保存计算出来的子问题的最优解。products[i]表示长度为i的绳子剪成若干段之后隔断成都的乘积的最大值，即。

注释2处，为什么这里products[2]等于2？例如当绳子长度为3的时候，我们剪成两段，其中一段为2，一段为1。这样长度为2的那段最大值就是2，而不是1，因为这一段我们不需要再剪了。

注释3处，初始化的时候为什么products[3]=3？因为当length<=3的时候，我们直接返回了结果。如果整个绳子的长度为3，我们必须把绳子剪开，因为题目要求m>1，其中一段为2，另一段为1，这样结果就是2。当length>=4的时候，我们可以把绳子剪成两段，其中一段为3,另一段为１，这样长度为3的那一段的最大值就是3而不是2，因为这一段我们不需要再剪了。当然长度为4的最大值是剪成2和2的组合，我们已经存储了2的长度。

注释4处，直接从j=1开始，不需要从0开始。

贪婪算法

贪婪算法和动态规划不一样。当我们应用贪婪算法解决问题的时候，每一步都可以做出一个贪婪的选择，基于这个选择，我们确定能够得到最优解。贪婪算法需要用数学的方式证明每一步的贪婪选择是正确的。

贪婪算法

1. 当 n>=5 时，尽可能多地剪长度为 3 的绳子
2. 当剩下的绳子长度为 4 时，就把绳子剪成两段长度为 2 的绳子。

证明：书上的证明。。。

1. 当 n>=5 时，可以证明 ，并且。也就是说，当绳子剩下长度大于或者等于 5 的时候，可以把它剪成长度为 3 或者 2 的绳子段。
2. 当 n>=5 时，，因此，应该尽可能多地剪长度为 3 的绳子段。
3. 当 n=4 时，剪成两根长度为 2 的绳子，其实没必要剪，只是题目的要求是至少要剪一刀。

/**
 *
 * @param length 绳子的长度
 * @return
 */
public static int maxProduceAfterCuttingGreedy(int length) {
    if (length < 2) {
        return 0;
    }
    if (length == 2) {
        return 1;
    }
    if (length == 3) {
        return 2;
    }
    //尽可能多的减去长度为3的绳子段，这个需要去证明，长度为3的段数越多乘积越大
    int timesOf3 = length / 3;
    //注释1处
    if (length - timesOf3 * 3 == 1) {
        timesOf3 -= 1;
    }
    int timeOf2 = (length - timesOf3 * 3) / 2;
    return (int) Math.pow(3, timesOf3) * (int) Math.pow(2, timeOf2);
}

注释1处，当绳子最后剩下的长度为4的时候，不能再减去长度为3的绳子段，此时更好的方法是把绳子减去长度为e的两段，因为2*2>3*1。

比如绳子长度为13:

1. 尽可能减长度为3的绳子，可以剪4段长度为3的绳子，还剩一根长度为1的绳子，最终乘积是：3*3*3*3*1 =81。
2. 尽可能减长度为3的绳子，可以剪3段长度为3的绳子，当绳子最后剩下的长度为4的时候，不能再减去长度为3的绳子段，最终乘积是：3*3*3*4 = 27 * 4 108。

参考链接：

• java算法-剪绳子
• 剑指 Offer 14- I. 剪绳子