343 整数拆分（数学、动态规划-递推）

1. 问题描述：

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

示例 1:

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

示例 2:

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

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/integer-break

2. 思路分析：

① 分析题目可以知道对于每一个正整数对应的最大乘积都是取决于分解为比他小的正整数的最大乘积，由小的范围可以递推出最大的范围，所以可以使用动态规划解决，所以对于当前的整数i拆分的最大乘积为在所有将i分解为若干个比i小的整数乘积的方案中的最大值，我们可以声明一个dp数组或者列表，dp[i]表示当前数字i拆分为若干个整数的最大乘积，dp[i]的值主要分为两种情况：

• 将i分解为j与i - j并且数字i - j不再拆分为其他的整数，最大乘积为j * (i - j)
• 将i分解为j与i - j并且数字i - j为拆分为若干个其他的整数，最大乘积为j* dp[i - j]

所以对于当前的dp[i]，枚举[0， j], j < i，判断分解为j与i - j对应上面的两种情况，在两种情况中取一个max即可，在枚举的时候其实相当于是枚举所有可能的分解方案（暴力枚举的优化），枚举的时候计算出当前的数字i分解为其他数字的最大乘积。

② 除了①中的思路我们我们还可以使用数学的思路进行求解，分析题目可以得到对于n = a1 + a2 + ... + ak，满足以下几个条件：

• 对于任意的ai都是小于5的，因为如果ai >= 5我们可以分解为 ai = 3 + （ai - 3），则乘积为  3 + （ai - 3）> ai的所以当ai为5的时候我们是可以将其分解为更小的数的
• 对于任意的ai都不等于1，因为分解为1还不如本身大
• 结合上面两个条件可知分解后的ai只能是2,3,4，对于4我们又可以将其分解为2,3所以最终只剩下2,3，而且最多是只能够有2个2，因为如果有3个2，2 + 2 + 2 = 3 + 3是可以将其分解为3 + 3的这个时候乘积更大

综上我们尽可能将ai分解为3，然后分解为2。

3. 代码如下：

数学：

class Solution:
    def integerBreak(self, n: int) -> int:
        # 因为n至少需要分解为两个数字所以需要特判一下
        if n <= 3: return 1 * (n - 1)
        p = 1
        while n >= 5:
            n -= 3
            p *= 3
        # 最后n只可能为2,3,4所以乘上n即可
        return p * n

动态规划（递推）：

class Solution:
    # 可以使用动态规划求解
    def integerBreak(self, n: int) -> int:
        dp = [0] * (n + 1)
        for i in range(2, n + 1):
            for j in range(1, i):
                dp[i] = max(dp[i], j * (i - j), j * dp[i - j])
        return dp[n]