难度: Medium
给定一个正整数 n ，将其拆分为 k 个 正整数 的和（ k >= 2 ），并使这些整数的乘积最大化。
返回 你可以获得的最大乘积 。
示例 1:
输入: n = 2 输出: 1 解释: 2 = 1 + 1, 1 × 1 = 1。
示例 2:
输入: n = 10 输出: 36 解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
提示:
2 <= n <= 58
Submission
运行时间: 17 ms
内存: 16.0 MB
class Solution:
def integerBreak(self, n: int) -> int:
dp = [0 for _ in range(n + 1)]
dp[2] = 1
for i in range(3, n + 1):
for j in range(1, i // 2 + 1):
dp[i] = max(dp[i], j * (i - j), dp[i - j] * j)
return dp[n]
Explain
这道题可以使用动态规划来解决。定义dp[i]为正整数i拆分成至少两个正整数之和的最大乘积。对于dp[i]，我们可以将i拆分成j和i-j，其中1<=j<i，则dp[i]等于j*(i-j)和j*dp[i-j]中的最大值。最终的答案即为dp[n]。
时间复杂度: O(n^2)
空间复杂度: O(n)
class Solution:
def integerBreak(self, n: int) -> int:
# dp[i]表示将正整数i拆分成至少两个正整数之和的最大乘积
dp = [0 for _ in range(n + 1)]
dp[2] = 1
for i in range(3, n + 1):
for j in range(1, i // 2 + 1):
# 将i拆分成j和i-j，取拆分后乘积的最大值
dp[i] = max(dp[i], j * (i - j), dp[i - j] * j)
# 返回将正整数n拆分后得到的最大乘积
return dp[n]
Explore
在整数拆分问题中，当整数为2时，唯一的拆分方法是1+1，其乘积为1。因此，`dp[2]`被初始化为1，表示将2拆分成两个正整数，其最大乘积是1。这是基础条件，为后续的动态规划迭代提供起始值。
考虑到`i`拆分成`j`和`i-j`时，乘积`j * (i-j)`与`i-j * j`相同，说明拆分的乘积与`j`和`i-j`的顺序无关。因此，只需考虑到`i // 2`即可避免重复计算。例如，拆分4为2+2和为3+1，其实3+1与1+3是相同的拆分（只是顺序不同），计算一次即可。
`j * (i - j)`考虑的是将`i`直接拆分为两部分`j`和`i-j`的乘积，而`dp[i - j] * j`考虑的是拆分`i-j`为多个数的最大乘积再乘以`j`。比较这两种情况可以确保得到将`i`拆分后的最大乘积，因为有时直接拆分不如进一步拆分`i-j`得到更大的乘积。
初始化为0是合理的，因为在动态规划中，`dp`数组的每个元素都会在迭代过程中被更新。初始化为0主要是为了确保在比较拆分乘积时，`dp`数组能够正确存储从0开始的比较结果。特别是对于`n`小于2的情况，虽然题目通常假定`n`至少为2，但如果处理更小的`n`，在实际应用中可能需要额外的边界条件处理。