NeetCode #682LC-343Medium1-D Dynamic ProgrammingNC 250
← Back to All Problems#682 · #343 · Integer Break(整数拆分)
📌 Problem Statement & Constraints
Given an integer
n, break it into the sum of at least two positive integers and maximise the product of those integers. Return the maximum product. Constraints: 2 <= n <= 58.💡 Core Algorithmic Approaches
- Let
dp[i]be the maximum product obtainable from breakingiinto at least two parts. - For each first part
jfrom 1 toi - 1, the remainder may be left whole (i - j) or broken further (dp[i - j]). - So
dp[i] = max(dp[i], j * (i - j), j * dp[i - j]). - The optimum uses as many 3s as possible with a 2 or 4 remainder, giving a closed form, but the DP is the general method.
💻 Benchmark Python3 Implementation
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):
# either stop at (i - j) or break it further
dp[i] = max(dp[i], j * (i - j), j * dp[i - j])
return dp[n]⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n^2): the nested loops over first part and remainder.
💾 Space Complexity
O(n): the DP array.
⚠️ Interview Pitfalls & Follow-ups
- Dropping the
j * (i - j)term: using onlyj * dp[i - j]undercounts because the remainder may be best left whole, as withi - j = 3. - Starting the inner loop at 0:
jmust be at least 1, since parts are positive integers. - Requiring distinct parts: parts may repeat, which is exactly why multiple 3s are used.
- Applying the all-3s rule without remainder handling:
n = 4should be 2 + 2 (product 4), not 3 + 1 (product 3).
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.