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。

解法1：数学方法

求函数的最大值，可得 x=e 时 y 最大，但只能分解成整数，故 x 取 2 或 3，由于6=2+2+2=3+3，显然，故应分解为多个3

class Solution:
    def integerBreak(self, n: int) -> int:
        if n==2:
            return 1
        elif n==3:
            return 2
        a = 1
        while n > 4:
            n -= 3
            a *= 3
        return a * n

注：当n==4时，while循环不执行，由于a==1，return an;刚好就是return 14 ==4

解法2：动态规划

使用动态规划，dp[i]为正整数 i 拆分后能返回的最大乘积。
最初转移方程为
本意是希望将 i 拆成 j 和 i-j，dp[j] 为 j 能获得的最大乘积，再与 i-j 相乘就得到了 i 拆分后的乘积。然鹅并不正确，因为 j 可以不做拆分。以 i = 5 为例，可以拆成 2+3 ，乘积为 6 ；但是按这个转移方程，dp[3]2 = 22 = 4，dp[2]3 = 1 3 = 3，是不对的。
正确的转移方程为

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