Approach Summary
dp[i] = max product from splitting i. For each j < i: dp[i] = max(dp[i], j*(i-j), j*dp[i-j]). Math insight: use as many 3s as possible.
How to Recognize This Pattern
- Split n into parts to maximise product
- Greedy insight: 3s beat 2s and never use parts ≥ 5
Complexity Analysis
Time Complexity
O(n²)
Space Complexity
O(n)
Tags
Math Dynamic Programming