343.整数拆分

给定一个正整数 n ，将其拆分为 k 个 正整数 的和（ k >= 2 ），并使这些整数的乘积最大化。

返回 你可以获得的最大乘积 。

示例 1：

1
2
3

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

示例 2：

1
2
3

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

提示：

2 <= n <= 58

来源：力扣（LeetCode）

链接：https://leetcode.cn/problems/integer-break/description/

思路

方法一：动态规划

dp数组代表 $i$ 拆分的最大积，可以把 $i$ 拆成 $j$ 和 $i-j$ （两个）以及 $j$ 和 $dp[i-j]$ （三个及三个以上）来实现。这里主要记录一种比较容易理解的数学方法，故不作精讲。

方法二：数学

这个方法来自于美版的美版的大佬StefanPochmann：

You’re making it pretty complicated.

If an optimal product contains a factor f >= 4, then you can replace it with factors 2 and f-2 without losing optimality, as 2*(f-2) = 2f-4 >= f. So you never need a factor greater than or equal to 4, meaning you only need factors 1, 2 and 3 (and 1 is of course wasteful and you’d only use it for n=2 and n=3, where it’s needed).

For the rest I agree, 33 is simply better than 22*2, so you’d never use 2 more than twice.

正整数 $4$ 可以拆分成 $2+2$ ，乘积不变( $4=2*2$ )。对于大于 $4$ 的正整数，总是存在一种拆分的方案，使得拆分成的两个正整数的乘积大于拆分前的正整数（例如， $5=2+3,5<2*3=6$ ）。

简单地说，假设最优结果中包含因子 $f>=4$ ，那么可以将其拆分成因子 $2$ 和( $f-2$ )；

又因为 $2*(f-2)=2*f-4>=f$ ，所以这种行为并不会失去最优性；

所以可以推导出永远不会使用 $>=4$ 的因子，即使用因子 $1,2,3$ ， $1$ 当然是应该被舍弃的。

我们可以直观的知道， $2$ 和 $3$ 的最小公倍数 $6$ ， $3*3$ 肯定比 $2*2*2$ 更优，所以不会出现三个 $2$ 。

数学归纳法可以得到上述结果。这里贴上力扣（Leetcode）官方题解

实现代码

动态规划：

class Solution {
public:
    int integerBreak(int n) {
        vector<int> dp(n + 1, 0);
        dp[1] = 1;
        for(int i = 2; i <= n; ++i){
            int m = i / 2;	//剪枝一半
            for(int j = 1; j <= m; ++j){
                dp[i] = max(dp[i], max(j * (i - j), j * dp[i - j]));
            }
        }
        return dp.back();
    }
};

时间复杂度： $O(n^2)$
空间复杂度： $O(n)$

数学

class Solution {
public:
    int integerBreak(int n) {
        //小于等于3需要单独处理
        if (n <= 3) {
            return n - 1;
        }
        int q = n / 3;
        int r = n % 3;
        //如果余数为0，说明因子全是3
        //余数为1，说明因子为3，3,...3，4
        //余数为2，说明因子3，3,...3，2
        if (r == 0) {
            return (int)pow(3, q);
        } else if (r == 1) {
            return (int)pow(3, q - 1) * 4;
        } else {
            return (int)pow(3, q) * 2;
        }
    }
};