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
}