343. Integer Break

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.

把一个整数拆分成多个整数相加，使得拆出来的数的乘积最大。
比如对于一个数n，假设从1到n-1的结果我们都知道了，现在要想找到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];
    }

但是经过数学推理发现，把数尽量拆成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;
};