66 剪绳子

题目描述

给你一根长度为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，这时候长length与宽width在什么情况下，达到面积s最大
s = length width
设length = x
则：width = n/2 - x
所以 s = x (n/2 - x)
= -x^2 + nx/2
求导s’ = -2x + n/2
s’ = 0 —> 得 x = n/4
(0,n/4)区间，s’>0,S单调递增
(n/4, n)区间，s’<0,S单调递减
n/4为极大值点
所以在长度x=n/4的时候，S的面积最大
width = n/2 - x
= n/2 - n/4
= n/4
所以width = length 的时候 s最大
通过一般性问题得出当定长的时候，截出的子段长度相等的时候，乘积最大
（通用性待数学求证）
回到本题
绳子长度为n，分成m分，那先设每分长度为x, 分数m=n/x
那么结果就是 n/x个 x 相乘 f(x)=x^(n/x)
求导：如下图

所以问题就回到了n/3的个数上面
当n能被3整除的时候，乘积=n^(n/3)
当n除3余1的时候，这时候发现多了一个1，这个1是不是很鸡肋，但是把前面的一个3拿出来，把这个一个1和前面一个3 分解为2和2，就变大了，所以乘积为 3^(n/3 - 1) 4
当n除3余2的时候，乘积为n^(n/3) * 2

代码一

public int cutRope(int target) {
        if(target<3)return target;
        if(target==3)return 2;
        int m = target%3;
        switch(m){
            case 0:
                return (int) Math.pow(3, target/3);
            case 1:
                return (int)Math.pow(3, target/3-1)*4;
            case 2:
                return (int)Math.pow(3, target/3)*2;             
        }
        return 0;
    }

代码二

思路：
递归 自顶向下
我们先定义函数f(n)为把绳子剪成若干段之后的各段长度乘积的最大值.在剪第一刀的时候,我们会有n-1种可能的选择,也就是说剪出来的第一段绳子的长度可能为1,2,……n-1.因此就有了递归公式 f(n) = max(f(i)*f(n-i)),其中0<i<n.

public int cutRope(int target) {
        if(target<2)return 0;
        if(target==2)return 1;
        if(target==3)return 2;
        return ItercutRope(target);
    }
    public int ItercutRope(int target) {
        int max = 0;
        for(int i = 0;i<target/2+1;i++) {
            max = Math.max(ItercutRope(i)* ItercutRope(target-i),max);
        }
        return max;
    }

代码三

思路：动态规划 自底向上
申请辅助空间arr来存放长度为n的分段乘积的max值，我们知道当绳子的长度小于4的时候，绳子的分段乘积max值是小于绳子长度本身的，所以我们在一开始的arr里面，当绳子长度小于4的时候我们存放绳子本身的长度。
我们有递归公式：f(n)=max(f(i)*f(n-i),) i为剪的某一段的长度。我们一开始从n=4,n=5,n=6一直计算到n=n;

public class Solution {
    public int cutRope(int target) {
       if(target<2)
            return 0;
        if(target==2)
            return 1;
        if(target==3)
            return 2;
        int[] arr = new int[target+1];
        int max = -1;
        arr[0] = 0;
        arr[1] = 1;
        arr[2] = 2;
        arr[3] = 3;
        for(int i=4;i<=target;i++) {
            for(int j=1;j<=i/2;j++) {
                int val = arr[j]*arr[i-j];
                max = max>val?max:val;
                arr[i] = max;
            }
        }
        max = arr[target];
        return max;
    }
}