题解 | #剪绳子#

题目描述

给你一根长度为n的绳子，请把绳子剪成整数长的m段（m、n都是整数，n>1并且m>1，m<=n），每段绳子的长度记为k[1],...,k[m]。请问k[1]x...xk[m]可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。
输入描述：输入一个数n，意义见题面。（2 <= n <= 60）
返回值描述：输出答案。
示例1
输入：8
返回值：18

题目分析

当绳子的长度长于2时，可以被剪成若干段，而这些段的长度可以是从1 ~ (绳子的长度-1)，可以使用暴力法，遍历绳子的所有切割方法，求出里面最大的乘积。

解题思路

方法1：暴力法，遍历可以分割的所有情况，取其中的最大值
在分析的思路里，对于子线段的长度范围是1 ~ (n-1)，实际上，只需要1 ~ (n/2)，因为大于n/2的情况，已经在前面出现过了，所以可以直接去掉。

方法2：数学推导，可以知道如何乘积最大的切割方式
推导过程：
1、根据“算数几何均值不等式”可知：当 n1+n2+n3+..na= 绳子总长度不变时，有

当且仅当n1=n2=n3..=na时，右边的值刚好能等于左边的值，不然都比左边值小；
则有推导结论1：当所有绳段长度相等时，乘积最大；

2、将绳子长度分为a段等长的x，满足 n = a*x，则绳子每段乘积为 x^a，因为 a= n/x，则有
x^a = x^(n/x) = (x^(1/x))^n，仅当(x^(1/x))取最大值时，乘积x^a为最大值。
对 y=x^(1/x) 求导，可知当且仅当 x = e时，导数y'=0（且x<e，y'>0递增；x>e，y'<0递减），则y在x=e处有极大值（呈峰状）；
因为绳子只能剪成整数长度，而x=e（2.7），可已经选择的较大值为2和3，比较y(2)和y(3)可知

取3的时候更大，其他的整数长度乘积都小于3；
则有推导结论2：最优的绳段长度为3；

实现过程：
1.当线段长度大于4时，优先分割长度为3的线段；
2.当长度小于等于4时，分割长度为2的线段。

代码实现

方法1：暴力遍历

public int cutRope(int target) {
    if(target<=1) return 1;
    if(target == 2) return 1;
    if(target == 3) return 2;
    int[] nums = new int[target+1];
    // 定义一些基本情况
    nums[0] = 1; nums[1] = 1; nums[2] = 2; nums[3] = 3;
    // 记录最大值
    int max = 0;
    for(int i=4;i<=target;i++){
        // 防止重复计算，只用计算到i/2
        for(int j=1;j<=i/2;j++){
            // 计算乘积
            int tmp = nums[j]*nums[i-j];
            if(tmp > max){
                max = tmp;
                nums[i] = max;
            }
        }
    }
    return max;
}

时间复杂度：O(n^2)，需要两次循环，总循环次数为n*n/2，时间复杂度为O(n^2)；
空间复杂度：O(n)，需要空间大小为n+1的辅助数组nums；

方法2：数学推导法

public int cutRope(int target) {
        // 将一些基本情况直接返回
        if(target == 2){
            return 1;
        }else if(target == 3){
            return 2;
        }
        // 计算target中能分割出多少个长度为3的线段
        int a1 = target / 3;
        if((target-a1*3) == 1){
            a1--;
        }
        // 计算剩下的分割长度为2的线段
        int a2 = (target-a1*3)/2;
        // 求这些长度为3和2的线段乘积
        int max = (int)Math.pow(3,a1) * (int)Math.pow(2,a2);
        return max;
    }

时间复杂度：O(1)，只需要计算即可，不用循环；
空间复杂度：O(1)，只需要常量的变量数存储结果和一些值；