Given a positive integer n, break it into the sum of at least two positive integers and maximize the product of those integers. Return the maximum product you can get.
For example, given n = 2, return 1 (2 = 1 + 1); given n = 10, return 36 (10 = 3 + 3 + 4).
Note: You may assume that n is not less than 2 and not larger than 58.

把一個整數(shù)拆分成多個整數(shù)相加，使得拆出來的數(shù)的乘積最大。
比如對于一個數(shù)n，假設從1到n-1的結果我們都知道了，現(xiàn)在要想找到n的結果：
就利用以前的結果把1+(n-1)到(n-1)+1都試一遍，找到最大的。

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

但是經過數(shù)學推理發(fā)現(xiàn)，把數(shù)盡量拆成3，拆不成就拆成2。這樣最大：

var integerBreak = function(n) {
    if (n===1) return 1;
    if (n===2) return 1;
    if (n===3) return 2;
    var res = 1;
    while (n>4){
        res*=3;
        n-=3;
    }
    if (n!==0)
        res*=n;
    return res;
};