剪绳子

题目：

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

分析：

​ 有两种方案解决这个问题，一种是 O(n^2) 时间复杂度和 O(n) 空间复杂度的动态规划。另一种是 O(1) 时间复杂度和空间复杂度的贪婪算法。

方案一：动态规划

​ 首先定义 f(n) 表示长度为 n 的绳子剪成若干段后的乘积最大值。在剪第一刀的时候，有 n-1 种选择，剪出第一段绳子的长度分别为 1, 2, 3, ..., n-1。因此 f(n) = max(f(i) * f(n-i)) 其中 0<i<n。

​ 这是一个从上到下的递归公式。因为递归会有很多重复的计算，一个更好的办法是按照从下到上的顺序计算。当绳子的长度为 2 时，只可能剪成长度为 1 的两段，因此 f(2) = 1。当长度为 3 时，可以剪成 1、2两段或者三段 1，因此 f(3) = 2。依此类推，可以得到如下代码：

public static int maxMul(int length) {
    //因为要求长度n>1,所以这里返回0表示输入非法
    if (length < 2) {
        return 0;
    }
    //长度为2时,因为要求剪下段数m>1,所以最大是1x1=1
    if (length == 2) {
        return 1;
    }
    //长度为3时,因为要求剪下段数m>1,所以最大是1x2=2
    if (length == 3) {
        return 2;
    }
    //运行至此,说明绳子的长度是>3的,这之后0/1/2/3这种子问题最大就是其自身长度
    //而不再需要考虑剪一刀的问题,因为它们剪一刀没有不剪来的收益高
    //而在当下这么长的绳子上剪过才可能生成0/1/2/3这种长度的绳子,它们不需要再减
    //所以下面的表中可以看到它们作为子问题的值和上面实际返回的是不一样的

    int[] sections = new int[length+1];

    sections[0] = 0;
    sections[1] = 1;
    sections[2] = 2;
    sections[3] = 3;

    int max = 0;
    for (int i = 4; i <= length; i++) {
        max = 0;
        //因为要计算f(j)乘以f(i-j)的最大值,j超过i的一半时是重复计算
        //所以只需要考虑j不超过i的一半的情况
        for (int j = 1; j <= i/2; j++) {
            int val = sections[j] * sections[i - j];
            if (max < val) {
                max = val;
            }
        }
        sections[i] = max;
    }
    //循环结束后,所求的f(length)也就求出来了
    max = sections[length];
    return max;
}

方案二： 贪心算法

​ 如果我们按照如下策略来剪绳子，则得到的各段绳子的乘积将最大： 当 n>=5 时，我们尽可能多地剪长度为 3 的绳子；当剩下的绳子长度为 4 时，把绳子剪成长度为 2 的绳子。这种思路对应代码如下：

public static int maxMulByGreedy(int length) {

    //因为要求长度n>1,所以这里返回0表示输入非法
    if (length < 2) {
        return 0;
    }
    //长度为2时,因为要求剪下段数m>1,所以最大是1x1=1
    if (length == 2) {
        return 1;
    }
    //长度为3时,因为要求剪下段数m>1,所以最大是1x2=2
    if (length == 3) {
        return 2;
    }
    // 长度为 3 的绳子段数
    int countOf3 = length / 3;

    // 当剩余绳子长度为 4的时候，剪成2x2的两段，不能再剪3
    if (length - countOf3 * 3 == 1) {
        countOf3--;
    }
    // 长度为 2 的绳子段数
    int countOf2 = (length - countOf3 * 3) / 2;
    return (int) (Math.pow(3, countOf3) * Math.pow(2, countOf2));
}