剑指offer-67-剪绳子

思路

不失一般性，首先想到dp，然后考虑状态转移方程
dp一般开始考虑数学归纳法: 0 1 2 3直接输出,4=2+2 ，5=2+ 3 ，6=3+3,7=3+4
假设c=a+b>=2sqrt(ab),当且仅当a==b时取等号。偶数直接分两半，奇数一个向下取整，一个向上取整。
这是两个数的时候,n个数，a1+a2+.....aN>=1/nsqrt(a1*a2....aN)
进一步发现：最终都可以分解为2和3了，并且3越多，乘积越大。
上面归纳3越多值越大是我看评论区的，真实情况是dp[i]=max(dp[i-2]2,dp[i-3]3);
参考3越多写了如下代码，为了炫技也写了只有一行的java代码

代码

switch写法

public class Solution {
    public int cutRope(int target) {
        switch (target%3){
                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;
    }
}

一行代码

public class Solution {
    public int cutRope(int target) {
        return target%3==0?(int)Math.pow(3,target/3):
        (target%3==1?(int)Math.pow(3,target/3-1)*4:(int)Math.pow(3,target/3)*2);
    }
}