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.

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.

暴力解就是loop所有可能的數字，然後把可以拆分的數loop一輪，j只需要loop到i/2因為，其他的數字i - j已經loop過。

// Brute Force Dynamic Programming
int integerBreak(int n) { // time: O(n^2); space: O(n)
    vector<int> dp(n + 1, 0);
    dp[1] = 1;
    for (int i = 2; i <= n; ++i) {
        for (int j = 1; j <= i / 2; ++j) {
            dp[i] = max(dp[i], max(j, dp[j]) * max(i - j, dp[i - j]));
        }
    }
    return dp.back();
}

把2到5的結果列出來之後，發現大於等於5的數n都可以拆分成3乘上(n - 3)。列出1到4的結果之後就可以用for loop把dp array計算出結果。

// DP + Math
int integerBreak(int n) { // time: O(n); space: O(n)
    if (n <= 2) return 1;
    if (n == 3) return 2;
    if (n == 4) return 4;
    vector<int> dp(n + 1, 0);
    dp[1] = 1;
    dp[2] = 1;
    dp[3] = 2;
    dp[4] = 4;
    for (int i = 5; i <= n; ++i) {
        dp[i] = 3 * max(i - 3, dp[i - 3]);
    }
    return dp.back();
}

大於4的數都偏向用3去拆分，因為有3的乘積比較大。譬如6可以等於2 + 2 + 2，乘積就是2 * 2 * 2 = 8，但6也等於3 + 3，乘積是3 * 3 = 9。

// Math
int integerBreak(int n) { // time: O(n); space: O(1)
    if (n == 2) return 1;
    if (n == 3) return 2;
    int res = 1;
    while (n > 4) {
        res *= 3;
        n -= 3;
    }
    res *= n;
    return res;
}