剪绳子【Java版】

方法一：数学函数求导法

【总体思路】构造函数求导，得到：m=n/e (小数的情况下)，也就是说尽量拆成一堆：2、3（最接近e的整数）

数学函数求导法：针对性规律
result= f(m) = (n/m) ^m，设n为定值，m为自变量，f(m)为乘积结果。
max{ f(m) }= max{ ln f(m) }，取对数。
求 ln f(m)= m*( ln n- ln m )最值点的m值，求导并令f(m)'=0，得到m=n/e.
e=2.718，然后因为取整数，所以是拆成一堆2、3；
具体看下：4>>>2x2；5>>>2x3；6>>>3x3 符合分析的结果。

public class Solution {
    public int cutRope(int target) {
        if(target == 2)return 1;//因为题目要求最少拆成2份
        if(target == 3)return 2;
        int res = 1;
        while(target > 4 ){//target剩<=4时，三种情况：4=>2*2=4; 3=>3; 2=>2; (-=3 不存在1)
            target -= 3;
            res *= 3;
        }
        return res * target;//三种情况合并处理
    }
}//时间O(N)，空间O(1)

方法二：动态规划

【总体思路】dp[] 存一步步的最优 + 找到 递推公式

public class Solution {
    int[] dp = new int[60];
    public int cutRope(int target) {
        if(target == 2) return 1;
        if(target == 3) return 2;//这里的策略不同，要单独拎出来
        dp[2] = 2;
        dp[3] = 3;//在target>=4的前提下，dp[]数组2~3对应的值（不必强制分两段）
        for(int i=4; i<=target; ++i){
            int max = Integer.MIN_VALUE;
            for(int j=2; j<=i-1; ++j){//果然，dp的本质是穷举
                if(max < dp[j]*(i-j)) max = dp[j]*(i-j);//动态规划重点是找到=>【最优子结构的递推公式】
            }//另一种递推：将上一行的（i-j）换成dp[i-j]
            dp[i] = max;
        }
        return dp[target];
    }
}//时间O(N^2)  空间O(N)