⚡Flashcard Drill➔
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

  1. Let dp[i] be the maximum product obtainable from breaking i into at least two parts.
  2. For each first part j from 1 to i - 1, the remainder may be left whole (i - j) or broken further (dp[i - j]).
  3. So dp[i] = max(dp[i], j * (i - j), j * dp[i - j]).
  4. 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 only j * dp[i - j] undercounts because the remainder may be best left whole, as with i - j = 3.
  • Starting the inner loop at 0: j must 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 = 4 should 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.
🎯 Drill This Card Now➔

🧩 Related 1-D Dynamic Programming Problems