Integer Break: The Math Insight That Makes DP Click

You are given an integer n. Your job is to break it into at least two positive integers that sum to n, then maximize their product. For n = 10, the best split is 3 + 3 + 4 = 10, which gives a product of 3 × 3 × 4 = 36.

This is LeetCode 343: Integer Break. It looks like a pure math puzzle at first, but there is a clean DP angle that makes it feel right at home next to problems like Climbing Stairs and House Robber. Once you see the pattern, the solution writes itself.

The math insight: why 3s win

Before jumping to code, it helps to understand why the answer always involves 3s (for large enough n).

Consider any factor you include in your product. If that factor is 1, it does not help at all. If it is 2 or 3, you are getting a solid multiplier. But once a factor hits 5 or more, you are better off splitting it further.

For example, compare keeping 6 as one piece versus splitting it:

• 6 as a single factor: contributes 6
• 6 split into 3+3: contributes 3 × 3 = 9

Splitting 6 into two 3s beats keeping it whole. The same logic applies to any number greater than or equal to 4: splitting it into smaller pieces gives a larger product.

What about 2 versus 3? Three 2s give 2 × 2 × 2 = 8, but two 3s give 3 × 3 = 9. So whenever you have three 2s, swap them for two 3s. That means 3 is the most efficient building block.

The conclusion:

• Use as many 3s as possible.
• If n mod 3 == 0: all 3s.
• If n mod 3 == 1: use one 4 (= 2+2, both multiplied) instead of a 3+1 (which adds a useless 1).
• If n mod 3 == 2: use one 2 at the end, rest are 3s.

For n = 10: 10 = 3 + 3 + 4, product = 36. That matches the diagram above.

The DP approach

The math insight is elegant, but a DP solution is often easier to reason about and extend. Define dp[i] as the maximum product you can get by breaking integer i into at least two parts.

The recurrence is: for each i, try every way to peel off a piece j from 1 to i-1. For each split, you can either:

• Keep j as a raw integer and multiply it by dp[i - j]
• Or keep j and also keep i - j raw (the "exactly two pieces" case)

In practice, because we know 2 and 3 are the only pieces worth using, you can simplify to:

dp[i] = max(dp[i-2] * 2, dp[i-3] * 3)

This covers all cases because you are always looking back exactly 2 or 3 positions, corresponding to peeling off a 2 or a 3 from i.

Python solution

def integer_break(n):
    if n <= 3:
        return n - 1
    dp = [0] * (n + 1)
    dp[1] = 1
    dp[2] = 2
    dp[3] = 3
    for i in range(4, n + 1):
        dp[i] = max(dp[i - 2] * 2, dp[i - 3] * 3)
    return dp[n]

A few things worth noticing here.

The base cases. For n = 2, you must split into 1 + 1, product = 1. For n = 3, you must split into 1 + 2, product = 2. You handle these before filling the table because the "keep the piece raw" logic does not apply when n is small enough that any split produces a smaller value.

Why dp[1] = 1, dp[2] = 2, dp[3] = 3 inside the table. These seed values represent the full value of that integer when it appears as a piece inside a larger break. When you split i = 5 into 2 + 3, the "3 piece" contributes 3 itself as a factor, not dp[3] = 2. So the table stores the best value each integer can contribute as a factor.

Why the recurrence uses dp[i-2] * 2 and dp[i-3] * 3. You are saying: "I peeled off a 2 (or 3) from i, and the remaining i-2 (or i-3) is broken optimally according to its own dp value." Because 2 and 3 are the only pieces worth taking, you only need these two comparisons.

Step-by-step walkthrough

Here is how the table fills in for n = 10:

Notice how the values grow quickly once 3s start stacking up. From dp[6] = 9 onward, each step is essentially multiplying the previous "best 3-back" value by 3.

Complexity analysis

You iterate through each index from 4 to n once, doing O(1) work per step. The DP array holds n + 1 values. Both are tight, and there is no way to do meaningfully better for the general case.

If you use the pure math approach (count 3s with modulo arithmetic), you get O(1) time and O(1) space. But the DP version is easier to understand, easier to verify, and naturally generalizes if the problem constraints change.

Edge cases

• n = 2: must split into 1 + 1. Product = 1. The early return handles this.
• n = 3: must split into 1 + 2. Product = 2. The early return handles this too.
• n = 4: split into 2 + 2. Product = 4. Both pieces contribute as raw factors, and dp[4] = 4 confirms this.

If your solution does not handle n = 2 and n = 3 explicitly, the general recurrence will produce wrong answers there because there is no valid way to break those further and keep both pieces greater than 0 in a meaningful sense.

Building blocks

This problem sits at the intersection of two reusable patterns.

Linear DP with a fixed lookback. The recurrence dp[i] = max(dp[i-2] * 2, dp[i-3] * 3) looks back exactly 2 or 3 positions. That is the same structure as Climbing Stairs (dp[i] = dp[i-1] + dp[i-2]) and House Robber (dp[i] = max(dp[i-1], dp[i-2] + nums[i])). Once you recognize this shape, filling a DP table becomes mechanical.

Math-guided DP initialization. The key move here is seeding dp[1] = 1, dp[2] = 2, dp[3] = 3 so that the DP "knows" the raw contribution of each piece. This is not just about base cases; it is about what each piece is worth when it appears inside a larger split. Getting initialization wrong is the most common source of bugs in this problem.

Other problems that use closely related building blocks:

• Climbing Stairs (LeetCode 70): same two-position lookback, additive transition instead of multiplicative.
• House Robber (LeetCode 198): same two-position lookback, max over two options.
• Coin Change (LeetCode 322): variable lookback (one per coin), but same "build up from smaller amounts" structure.

From understanding to recall

The logic here clicks on a first read. But reproducing it in an interview without any hints is another skill entirely. You need to remember:

• Why 3 beats 2 (three 2s vs two 3s: 8 vs 9)
• Why the base case is n - 1 for small n
• Why the seed values inside the table are different from the early return values
• Why the recurrence uses multiplication rather than addition

Each of those is a small but distinct piece of knowledge. Spaced repetition helps you lock them in one at a time, revisiting at increasing intervals until the whole solution flows without effort. That is what turns "I understood this post" into "I can write it cold in 10 minutes."

Related posts

• Climbing Stairs - The best first DP problem: same linear-lookback pattern with an additive transition
• Coin Change - Variable lookback DP built on the same "optimal substructure" idea
• House Robber - Two-position lookback DP with a max transition, the closest sibling to Integer Break