剪绳子

1 递归

public class Solution {
    public int cutRope(int target) {
        if(target < 4)
            return target-1;
        return getMax(target);
    }
    public int getMax(int target){
        if(target < 4)
            return target;
        int n1 = 2 * (target-2);
        int n2 = 3 * (target-3);
        return n2 > n1 ? n2 : n1;
    }
}

通过递归可以很容易看出，最后的结果就是x个3和y个2相乘。
那x和y怎么确定呢，3越多越大还是2越多越大，还是说3和2的搭配有种奇妙的关系呢？

结论如下：

当 n>5 时，我们尽可能多地剪长度为 3 的绳子；当剩下的绳子长度为 4 时，把绳子剪成两段长度为 2 的绳子。

因此就有了第二种解法。

2 贪婪

public int cutRope(int target) {
        if(target < 4)
            return target-1;
        int timesOf3 = target/3;
        if(target - 3*timesOf3 == 1)
            timesOf3 -= 1;
        int timesOf2 = (target - 3*timesOf3)/2;
        return (int)Math.pow(3,timesOf3)*(int)Math.pow(2,timesOf2);
    }