【剑指Offer】14. 剪绳子

n = 2
return 1 (2 = 1 + 1)

n = 10
return 36 (10 = 3 + 3 + 4)

public class Solution {
    /**
    * 解题思路，找出最优解的规律
    * 当target等于1，2，3的时候，结果是固定的
    * 当target大于3的时候，可以看以下数据
    * target=4, 最优解：2 2
    * target=5, 最优解：3 2
    * target=6, 最优解：3 3
    * target=7, 最优解：3 2 2
    * target=8, 最优解：3 3 2
    * target=9, 最优解：3 3 3
    * target=10,最优解：3 3 2 2
    * target=11,最优解：3 3 3 2
    * target=12,最优解：3 3 3 3
    * target=13,最优解：3 3 3 2 2
    * target=14,最优解：3 3 3 3 2
    * target=15,最优解：3 3 3 3 3
    *
    * 所以不难发现3和2的个数规律
    */
    public int cutRope(int target) {
        if(target < 2)
            return 0;
        if(target == 2)
            return 1;
        if(target == 3)
            return 2;
        
        int of3 = target / 3;
        if(target - of3 * 3 == 1)
            of3--;
        int of2 = (target - of3 * 3) / 2;
        
        return (int)(Math.pow(3, of3)) * (int)(Math.pow(2, of2));
    }
}

public class Solution {
    public int cutRope(int n) {
        int[] dp = new int[n + 1];
        dp[1] = 1;
        for (int i = 2; i <= n; i++)
            for (int j = 1; j < i; j++)
                dp[i] = Math.max(dp[i], Math.max(j * (i - j), dp[j] * (i - j)));
        return dp[n];
    }
}