剪绳子

《剑指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。

思路：有两种不同的方法解决这个问题。
1、动态规划：时间复杂度O（n^2）;空间复杂度：O（n）。
   定义函数f(n)为把长度为n的绳子剪成若干段后各段长度乘积的最大值。在剪第一刀时，有n-1种选择，即剪出的第一段绳子长度可能为1,2,3,...,n-1。因此 f ( n ) = max( f ( i ) * f ( n - i ) )，其中0<i<n。
   例如：绳子最初的长度为10，我们可以把绳子剪成长度分别为4和6的两段，也就是f(4)和f(6)都是f(10)的子问题。接下来分别求解这两个子问题。我们可以把长度为4的绳子剪成均为2的2段，即f(2)是f(4)的子问题。同样，我们也可以把长度为6的绳子剪成长度分别为2和4的两段，即f(2)和f(4)都是f(6)的子问题。我们注意到f(2)是f(4)和f(6)的公共的更小的子问题。

2、贪心算法：时间复杂度O（1）;空间复杂度O（1）
   当n >= 5 时，2（n - 2）> n并且3（n - 3）> n。也就是说当绳子剩下的长度大于或等于5时，剪成长度为3或2的绳子段。另外，n >= 5时，3（n-3）>= 2（n - 2），所以应该尽可能多剪长度为3的绳子段。

代码如下：

// 动态规划
public int maxProductAfterCuttingSolution1 (int length) {
    if (length < 2) {
        return 0;
    }
    if (length == 2) {
        return 1;
    }
    if (length == 3) {
        return 2;
    }
    int[] products = new int[length + 1];
    // 这里设置的0,1,2,3位置上的数是为了便于计算。
    // 当i大于等于4时，数组中第i个元素表示把长度为i的绳子剪成若干段之后各段长度乘积的最大值
    products[0] = 0;
    products[1] = 1;
    products[2] = 2;
    products[3] = 3;
    int max;
    for (int i = 4;i <= length;i++) {
        max = 0;
        for (int j = 1;j < i/2;j++) {
            int product = products[j] * products[i - j];
            if (max < product) {
                max = product;
                products[i] = max;
            }
        }
    }
    return products[length];
}

// 贪心算法
public int maxProductAfterCuttingSolution2(int length) {
    if (length < 2) {
        return 0;
    }
    if (length == 2) {
        return 1;
    }
    if (length == 3) {
        return 2;
    }
    // 尽可能多的剪出长度为3的绳子
    int timesOfThree = length / 3;
    // 当绳子最后剩下的长度为4时（剩下长度为1），不能再减去长度为3的绳子
    if ((length - timesOfThree * 3) == 1) {
        timesOfThree -= 1;
    }
    // 长度为2的绳子
    int timesOfTwo = (length - timesOfThree * 3) / 2;
    return (int)(Math.pow(2,timesOfTwo) + Math.pow(3,timesOfThree));
}