343. Integer Break

Question

Given an integer n, break it into the sum of k positive integers, where k >= 2, and maximize the product of those integers.

Return the maximum product you can get.

Solution

动态规划，用数组dp[]记录最大乘积。
在n < 4之前为特例，由于必须拆分，因此乘积小于自身。但由于之后的数字要用到拆分的特性，因此这三个数字要特殊设置为自身。
在此之后，每个数字可以拆分成两个数的加和，然后乘积等于对应两个数的乘积。
（dp[4]可以不设置计算得出，但是指定值的话可以加快速度。）

Code

class Solution {
    public int integerBreak(int n) {
        if(n <= 1) return 0;
        if(n == 2) return 1;
        if(n == 3) return 2;
        int[] dp = new int[n+1];
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 3;
        dp[4] = 4;
  
        for(int i = 4; i <= n; i++){
            for(int j = 1; j <= (i/2)+1; j++){
                int k = i - j;
                dp[i] = Math.max(dp[i], dp[j] * dp[k]);
            }
        }
        return dp[n];
    }
}

Solution 2

数学方法，当两数之和大于4时，拆分成两个更小的加和可以得到更大的乘积。
而当等于4时，可以拆分为两个2相乘。
因此，最终有意义的拆分结果只会有2和3。

拆分规则：

1. 最优： 3 。把数字 n 可能拆为多个因子 3 ，余数可能为 0,1,2 三种情况。
2. 次优： 2 。若余数为 2 ；则保留，不再拆为 1+1 。
3. 最差： 1 。若余数为 1 ；则应把一份 3+1 替换为 2 + 22+2，因为 2 * 2 > 3 * 1

Code

class Solution {
    public int integerBreak(int n) {
        if (n <= 3) {
            return n - 1;
        }
        int quotient = n / 3;
        int remainder = n % 3;
        if (remainder == 0) {
            return (int) Math.pow(3, quotient);
        }
        else if (remainder == 1) {
            return (int) Math.pow(3, quotient - 1) * 4;
        }
        else {
            return (int) Math.pow(3, quotient) * 2;
        }
    }
}

Solution 3

同样，我们可以将之前的结论用在动态规划上，j只取2或3，将时间复杂度从O(n^2)降低到O(n)。

Code

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