### Integer Break: Unraveling Dynamic Programming

Here is the problem, by Leetcode. First try to think of the brute-force approach. https://leetcode.com/problems/integer-break/description/ Given a positive integer n , break it into the sum of at least two positive integers and maximize the product of those integers. Return the maximum product you can get. Example 1: Input: 2 Output: 1 Explanation: 2 = 1 + 1, 1 × 1 = 1. Example 2: Input: 10 Output: 36 Explanation: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36. Note : You may assume that n is not less than 2 and not larger than 58. The brute-force will certainly be exponential. This problem is screaming for a DP solution, but coming up with exactly the "formula" for it is the challenge. Here is the way that I thought about the problem: as always, DP will be a construction approach, hence we'll build the solution for 1, 2, 3, ...., all the way to N, in our case N <= 58. Let's focus on a certain number N. One possibility is clear: the solution for N might