LeetCode 343.整数拆分（Integer Break）非动态规划解法的数学原理学术性探究

Great question! Let's unpack this key observation step by step—first proving the property mathematically, then explaining why it's the foundation of an optimal non-DP solution.

1. Mathematical Proof That 3*(n-3) > n for n > 4 #

Let's start with basic algebra to verify the inequality:

• Compute the difference between the two expressions: 3*(n-3) - n = 3n - 9 - n = 2n - 9
• For n > 4, substitute the smallest integer in this range (n=5): 2*5 -9 =1 >0
• As n increases beyond 5, 2n-9 only grows larger (since the coefficient of n is positive).

This means for every integer n greater than 4, splitting it into 3 and (n-3) will always yield a larger product than keeping n as a single term.

2. Why This Property Drives the Optimal Solution #

The goal of the integer break problem is to maximize the product of integers that sum to n. Here's why prioritizing 3s works:

• 3 is the most efficient number for maximizing product: Let's compare splitting into smaller integers:
  • Splitting 4 into 2+2 gives a product of 4, which is the same as keeping 4 intact—no gain, no loss.
  • Splitting 5 into 3+2 gives a product of 6, which is larger than 5 or splitting into 2+2+1 (product 4).
  • Splitting 6 into 3+3 gives a product of 9, which is larger than splitting into 2+2+2 (product 8) or any other combination.
• Iterative splitting is safe: If (n-3) is still greater than 4, we can repeat the process—split (n-3) into 3 and (n-6), and so on. Each split increases the total product, so we keep going until we're left with a remainder that's ≤4 (2, 3, or 4). These remainders don't need further splitting because their maximum product is themselves (or 2+2 for 4, which equals 4).

Example Walkthrough #

Let's take n=7:

• Split 7 into 3 + 4 → product is 3*4=12
• Since 4 ≤4, we stop. This is better than splitting into 2+2+3 (same product) or any other combination like 2+5 (product 10).

For n=8:

• Split 8 into 3 +5 → product so far 3*5=15
• Then split 5 into 3+2 → total product 332=18, which is the maximum possible.

内容的提问来源于stack exchange，提问作者Mike Chan