### 343. Integer Break

Given an integer n, break it into the sum of k positive integers, where k >= 2, and maximize the product of those integers.

Return the maximum product you can get.

Example 1:

Input: n = 2Output: 1Explanation: 2 = 1 + 1, 1 × 1 = 1.

Example 2:

Input: n = 10Output: 36Explanation: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36.
• Constraints:
• 2 <= n <= 58

### Analyze

n 拆分若干数后的乘积可拆分为: 1 * integerBreak(n - 1)2 * integerBreak(n - 2) ..., x * integerBreak(n - x)

n === 21 * 1
n === 31 * integerBreak(2)
n === 41 * integerBreak(3)2 * integerBreak(2)
n === 51 * integerBreak(4)2 * integerBreak(3)
• 递归思路(自顶向下)如下
/** * @param {number} n * @return {number} */var cache = {}var integerBreak = function(n) {  if (n === 1) return 1  if (cache[n]) return cache[n]  let result = 0  // here the i means for the value to be subtracted  for (let i = 1; i < n; i++) {    if (i > n - i) {      break    }    result = Math.max(result, i * Math.max(integerBreak(n - i), n - i))  }  return cache[n] = result}
• 接着使用动态规划(自底向上)思路实现:
/** * @param {number} n * @return {number} */var cache = {  1: 1}var integerBreak = function(n) {  if (n === 1) return 1
let result = 0  // here the i means for the value to calc  for (let i = 2; i <= n; i++) {    // here the m means for the value to be subtracted    for (let m = 1; m < i; m++) {      result = Math.max(result, m * Math.max(cache[i - m], i - m))    }    cache[i] = result  }
return result}