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.

Example 1:

Input: 2
Output: 1
Explanation: 2 = 1 + 1, 1 × 1 = 1.

Example 2:

Input: 10
Output: 36
Explanation: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36.

Note: You may assume that n is not less than 2 and not larger than 58.

Credits:
Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.

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

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

class Solution3{
public:
    int integerBreak(int n){
        vector<int> dp{0,0,1,2,4,6,9};
        for(int i = 7; i <= n; ++i)
            dp.push_back(3*dp[i-3]);

        return dp[n];
    }
};

参考：

1，https://www.cnblogs.com/grandyang/p/5411919.html