0343：整数拆分（★）

力扣第 343 题

题目

给定一个正整数 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

相似问题：

• 1808：好因子的最大数目（2070 分）

分析

#1

可以按最后一个拆分的数递推。注意 2 和 3 的特殊性。

1
2
3
4
5
6

class Solution:
    def integerBreak(self, n: int) -> int:
        f = list(range(n+1))
        for i in range(2,n+1):
            f[i] = max(f[i],max(f[j]*f[i-j] for j in range(1,i)))
        return f[-1] if n>=4 else n-1

41 ms

#2

还可以利用数学知识：

• 假如拆分出的某个数 x>=4
  • 那么将 x 拆为 2 和 x-2，2*(x-2)>=x，乘积不变或增大
• 因此必然存在最佳方案，拆出的数都是 2 或 3
• 3 个 2 换成 2 个 3，乘积更大，因此优先拆 3
• 根据 n%3 的值，即可确定最佳方案：
  • n%3 == 0 时，全拆为 3
  • n%3 == 1 时，拆为 2 个 2，剩下的都为 3
  • n%3 == 2 时，拆为 1 个 2，剩下的都为 3

解答

1
2
3
4
5
6

class Solution:
    def integerBreak(self, n: int) -> int:
        if n<4:
            return n-1
        q,r = divmod(n,3)
        return pow(3,q-1)*4 if r==1 else pow(3,q)*(1+(r==2))

23 ms