What is the best way to break an integer to maximize the product?

The most efficient way is to break the integer into as many 3s as possible and handle any remainder with 2s.

How does dynamic programming help in solving the Integer Break problem?

Dynamic programming stores intermediate results to avoid redundant calculations, allowing for an efficient solution to the problem.

What is the time complexity of solving the Integer Break problem using dynamic programming?

The time complexity is `O(n)` due to the need to compute the maximum product for each number up to `n` only once.

Can this problem be solved in less than `O(n)` time?

No, the solution involves processing each value up to `n` to find the optimal breakdown, so `O(n)` is the best achievable time complexity.

What is the space complexity of the Integer Break dynamic programming approach?

The space complexity is `O(n)` as it requires storage for intermediate results for each integer from 1 to `n`.

#343

Medium

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

整数拆分

给定一个正整数 n ，将其拆分为 k 个正整数的和（ k >= 2 ），并使这些整数的乘积最大化。返回你可以获得的最大乘积。示例 1: 输入: n = 2 输出: 1 解释: 2 = 1 + 1, 1 × 1 = 1。示例 2: 输入: n = 10 输出: 36 解释: 10 = 3…

数学动态规划

题目描述

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

lightbulb

解题思路

方法一：动态规划

我们定义 $f[i]$ 表示正整数 $i$ 拆分后能获得的最大乘积，初始时 $f[1] = 1$ 。答案即为 $f[n]$ 。

考虑 $i$ 最后拆分出的数字 $j$ ，其中 $j \in [1, i)$ 。对于 $i$ 拆分出的数字 $j$ ，有两种情况：

将 $i$ 拆分成 $i - j$ 和 $j$ 的和，不继续拆分，此时乘积为 $(i - j) \times j$ ；
将 $i$ 拆分成 $i - j$ 和 $j$ 的和，继续拆分，此时乘积为 $f[i - j] \times j$ 。

因此，我们可以得到状态转移方程：

f[i] = \max(f[i], f[i - j] \times j, (i - j) \times j) \quad (j \in [0, i))

最后返回 $f[n]$ 即可。

时间复杂度 $O(n^2)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为给定的正整数。

1

2

3

4

5

6

7

8

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

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Does the candidate recognize the optimal use of 3s to maximize the product?
question_mark
Can they effectively use dynamic programming or memoization to solve the problem efficiently?
question_mark
Are they able to optimize the solution for larger values of `n` without redundant calculations?

warning

常见陷阱

外企场景

error
Forgetting that the product is maximized by breaking `n` into 3s and 2s, not just splitting `n` evenly.
error
Overcomplicating the problem by attempting brute-force enumeration instead of dynamic programming.
error
Not considering edge cases like `n = 2` or `n = 3` where the breakdown may seem trivial but is important.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Generalizing to finding the maximum product for other mathematical break-downs, such as sums of squares.
arrow_right_alt
Changing the problem constraints to allow for fractional parts, altering the breakdown strategy.
arrow_right_alt
Adapting this problem to work with larger constraints like `n = 100` and ensuring that the solution still works efficiently.

help

常见问题

外企场景

继续练习

#357 统计各位数字都不同的数字个数 #368 最大整除子集 #313 超级丑数