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 = 2
Output: 1
Explanation: 2 = 1 + 1, 1 × 1 = 1.

Example 2:

Input: n = 10
Output: 36
Explanation: 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 === 2
1 * 1

n === 3
1 * integerBreak(2)

n === 4
1 * integerBreak(3)
2 * integerBreak(2)

n === 5
1 * 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
}