JZ67：剪绳子

解法1：动态规划

• 当n=1时，最大乘积只能为0；
• 当n=2时，最大乘积只能为1；
• 当n=3时，最大乘积只能为2；
• 当n=4时，可以分为如下几种情况:1111，121，13，2*2，最大乘积为4；
• 往下推时，发现n≥4时，可以把问题变成几个小问题，即：如果把长度n绳子的最大乘积记为f(n)，则有：f(n)=max(f(i)*f(n-1))，0<i<n。所以思路就很容易出来了：从下往上推，先算小的问题，再算大的问题，大的问题通过寻找小问题的最优组合得到。

其实这就是动态规划法，以下是动态规划法的几个特点：

1. 求一个问题的最优解
2. 整体问题的最优解依赖各子问题的最优解
3. 小问题之间还有相互重叠的更小的子问题
4. 为了避免小问题的重复求解，采用从上往下分析和从下往上求解的方法求解问题

public int cutRope(int target){
        if(target==1){
            return 0;
        }
        if(target==2){
            return 1;
        }
        if(target==3){
            return 2;
        }

        int[] product=new int[target+1];
        // 下面几个不是乘积，因为其本身长度比乘积大
        product[0]=0;
        product[1]=1;
        product[2]=2;
        product[3]=3;
        for(int i=4;i<=target;i++){
            int max=0;
            // 算不同子长度的乘积，找出最大的乘积
            for(int j=1;j<=i/2;j++){
                if(max<product[j]*product[i-j]){
                    max=product[j]*product[i-j];
                }
            }
            product[i]=max;
        }
        return product[target];
    }

解法2：贪心

贪婪算法依赖于数学证明，当绳子大于5时，尽量多地剪出长度为3的绳子是最优解。

public class Solution {
    public int cutRope(int target) {
        if(target<1){
            return 0;
        }
        if(target==2){
            return 1;
        }
        if(target==3){
            return 2;
        }
        int count3=target/3;
        int count2=0;
        if(target%3==1){
            count3--;
        }
        count2=(target-count3*3)/2;
        return (int)(Math.pow(3,count3)*Math.pow(2,count2));
    }
}

解法3：暴力递归（超时）

public class Solution {
    public int cutRope(int target) {
        if(target<1){
            return 0;
        }
        if(target==2){
            return 1;
        }
        if(target==3){
            return 2;
        }
        return getResult(target);
    }

    public int getResult(int target){
        if(target<4){
            return target;
        }
        int max=Integer.MIN_VALUE;
        for(int i=1;i<=target/2;i++){
            max=Math.max(max,i*getResult(target-i));
        }
        return max;
    }
}