题目分析

整数拆分问题是一个数学问题，如果指定拆分个数是2个的话，那么就是小伙伴们小学都学过的问题，可能小伙伴们会抬杠，小学怎么可能学过求二次函数最大值的问题呢？其实二拆分这个问题有另外一种描述：同样周长的正方形和长方形哪一个面积更大？Leetcode这一题将二拆分进行了推广，不指定拆分个数，这应该怎么做呢？暴力穷举当然是不行的，这是指数级的时间复杂度，应该如何优化呢？

DP

我们使用动态规划进行求解，dp[i]表示第i个数分解可得的最大值，可以得到状态转移方程
$$dp[i] = \max_{j = 1}^{i}(dp[i], dp[j] \times (i - j), j \times (i - j))$$
这个方案不难想到，小伙伴们千万不要忘记还有$i \times j$，DP的时间复杂度为$O(n^2)$，空间复杂度为$O(n)$，因为数字较小，因此很容易通过。

class Solution:
    def integerBreak(self, n):
        dp = [0] * (n + 1)
        for i in range(2, n + 1):
            for j in range(1, i):
                dp[i] = max(dp[j] * (i - j), j * (i - j), dp[i])
        return dp[-1]

数学方法

这个方法很巧妙，用一种归纳的方法进行这类问题的求解。有很多算法题，有一些较好的数学解法，这个题目可以给小伙伴们提供一个思路。
我们观察，如果一个数大于等于4，它的因子会出现什么情况？

可不可能出现大于等于4的因子？答案是不可能的，假设存在这样一个数x，满足$x \ge 4$，那么$2(x - 2) \ge x$在x大于等于4时恒成立，因此可以进行拆分。
2的个数不会超过3个，因为3个2的乘积为8，小于2个3的乘积9，因此如果可以拆分成3个2，那么不如拆分成2个3.

在大于等于5的情况中，不可能出现1，假设存在这样一个数x，满足$x - 1 \ge 4$，那么x - 1可以拆分成至少2个数，因此在其中一个增加1，乘积都会变大，所以不可能出现1的情况。
综上所述，当x大于等于5时，其因数只可能是2和3，且2的个数只能是0个，1个，2个，其余都是3，如果模3等于0，说明全部都是3，如果模3等于1，说明有2个2，如果模3等于2，说明有1个2。这种算法的时间复杂度为$O(1)$，空间复杂度为$O(1)$。

class Solution:
    def integerBreak(self, n: int) -> int:
        if n <= 3:
            return n - 1
        k, r = n // 3, n % 3
        if r == 0:
            return 3 ** k
        elif r == 1:
            return 3 ** (k - 1) * 4
        else:
            return 3 ** k * 2

刷题总结

数学方法往往很难想到，这道题目数据量较小，因此可以通过DP求解，如果这题的n非常大，那么就需要我们考虑数学方法，现在笔试的数据越来越庞大了，小伙伴们要加油呀。