整数拆分

343. 整数拆分

给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。

示例 1:

输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1。

示例 2:

输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。

说明: 你可以假设 n 不小于 2 且不大于 58。

方法一：动态规划

对于任意正整数 n，我们至少可以将其拆分为两个正整数的和。令 k 是拆分出来的第一个正整数，剩下的部分是 n - k，n - k 可以选择「不拆分」和「继续拆分」，是否拆分取决于这两个选择哪一个的最大乘积最大。

创建 dp 数组，dp[i] 表示将正整数 i 拆分为至少两个正整数的和之后，这些正整数的最大乘积。0 和 1 都不能进行拆分 所以 dp[0] = dp[1] = 0。

当 i >= 2 时，假设对正整数 i 拆分出的第一个正整数是 j (1 <= j < i)，有以下两种选择：

• i - j 不继续拆分，此时的乘积是 j * (i - j)
• i - j 继续拆分，此时的乘积是 j * dp[i - j]

我们取这两者的最大值，得到状态转移方程：
$$
dp[i] = \max_{1\leq j <i}{j \times max((i - j), dp[i - j])}
$$
最终结果为 dp[n]。

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

时间复杂度O(n^2)，空间复杂度O(n)。

方法二：数学

将 n 拆分成最多的 3 和 2，但是不能出现 1。

例如当 n = 10 时，最多的 3 的拆分方法为 3331，但是由于 1 对结果没有贡献，将最后的 31 改成 2*2。

class Solution {
    public int integerBreak(int n) {
        if(n <=3 )return n-1;
        
        int x = n / 3, b = n % 3;
        if(b == 0) return (int)Math.pow(3, x);
        //如果最后的余数为 1 ，代表存在 3*1这种情况，要改为 2*2
        if(b == 1) return (int)Math.pow(3, x-1)*4;
		//余数为 2 
        return (int)Math.pow(3,x)*2;
    }
}

时间复杂度O(1)，空间复杂度O(1)。