0343. Integer Break (M)

题目

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.

题意

将一个正整数拆成至少两个正整数的和，使得拆分出来的正整数之积最大。

思路

经验告诉我们，当一个正整数被拆成n个整数时，积最大时这n个整数应该相等(或相近)，如10拆成2个整数时，55最大，拆成3个时，334最大，拆成4个时，2233最大…所以我们只要从n=2开始递增，求出积变化情况的极大值即可。

打一张表找一下规律：

可以看到当n大于4时，最大积的情况都是将n拆成尽可能多的3，且除3外只能有一个2或者一个4。该规律的证明可参考《平分一个数，使得各份相乘所得到的积最大》。

也可以使用动态规划：dp[i]代表正整数i拆分后能得到的最大积，i可以被拆分为2个或更多的整数，拆分为两个时得到的积为j(i-j)，拆分为多个时可得到的积为jdp[i-j]。状态转移方程为：

代码实现

Java

极大值

class Solution {
    public int integerBreak(int n) {
        int pre = 0;
        int count = 2;
        while (count <= n) {
            int num = n / count;
            int remain = n % count;        // 存在余数时，要将余数中的每一个1都分配到num上以求积最大化
            int cur = (int) Math.pow(num, (count - remain)) * (int) Math.pow((num + 1), remain);
            if (cur >= pre) {
                pre = cur;
            } else {
                return pre;
            }
            count++;
        }
        return pre;
    }
}

找规律

class Solution {
    public int integerBreak(int n) {
        if (n == 2 || n == 3) {
            return n - 1;
        }
        int cnt3 = n / 3;
        int remain = n % 3;
        if (remain == 1) {
            return (int) Math.pow(3, cnt3 - 1) * 4;
        } else {
            return (int) Math.pow(3, cnt3) * (remain == 2 ? 2 : 1);
        }
    }
}

动态规划

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

参考