Integer Break

题目来源
把一个数拆分成多个数，使得其乘积最大。
一个方法是DP的方法，这个DP递推过程说实话我没有想到，代码如下：

class Solution {
public:
    int integerBreak(int n) {
        vector<int> dp(n+1);
        dp[2] = 1;
        for (int i=2; i<=n; i++)
            for (int j=1; j<i; j++)
                dp[i] = max(dp[i], max(dp[i-j], i-j) * max(dp[j], j));
        return dp[n];
    }
};

一个是利用数学知识证明，只有当2，或者3时候最大，并且2的个数不能大于两个，因为2*2*2 < 3*3。

(N/2)*(N/2)>=N, then N>=4
(N-1)/2 *(N+1)/2>=N, then N>=5
These two expressions mean that factors should be less than 4, otherwise we can do the break and get a better product. The factors in last result should be 1, 2 or 3. Obviously, 1 should be abandoned. Thus, the factors of the perfect product should be 2 or 3.

class Solution {
public:
    int integerBreak(int n) {
        if (n == 2)
            return 1;
        if (n == 3)
            return 2;
        int product = 1;
        while (n > 4) {
            product *= 3;
            n -= 3;
        }
        product *= n;
        return product;
    }
};