343. 整数拆分

[buuing]

给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。

示例 1:

输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1。

示例 2:

输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。

说明: 你可以假设 n 不小于 2 且不大于 58。

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/integer-break 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

---

推导最优子结构, 可以进行复用的部分

! dp[3] => 2
1*2     = 2
1*dp[2] = 1

! dp[4] = 4
1*3     = 3
1*dp[3] = 2
2*2     = 4
2*dp[2] = 2

! dp[5] = 6
1*4     = 4
1*dp[4] = 4
2*3     = 6
2*dp[3] = 4

! dp[6] = 9
1*5     = 5
1*dp[5] = 6
2*4     = 8
2*dp[4] = 8
3*3     = 9
3*dp[3] = 6

! dp[7] = 12
1*6     = 6
1*dp[6] = 9
2*5     = 10
2*dp[5] = 12
3*4     = 12
3*dp[4] = 12

! dp[8] = 18
1*7     = 7
1*dp[7] = 12
2*6     = 12
2*dp[6] = 18
3*5     = 15
3*dp[5] = 18
4*4     = 16
4*dp[4] = 16

! dp[9] = 27
1*8     = 8
1*dp[8] = 18
2*7     = 14
2*dp[7] = 24
3*6     = 18
3*dp[6] = 27
4*5     = 20
4*dp[5] = 24

• 记忆化递归

const integerBreak = n => {
  const memo = [0, 1]
  const dfs = (n) => {
    if (!memo[n]) {
      let max = 0
      for (let i = 1; i <= n - i; i++) {
        let k = n - i
        max = Math.max(max, i * k, i * dfs(k))
      }
      memo[n] = max
    }
    return memo[n]
  }
  return dfs(n)
}

• 动态规划

const integerBreak = n => {
  const dp = [0, 1]
  for (let i = 2; i <= n; i++) {
    let max = dp[i - 1]
    for (let j = 1; j <= i - j; j++) {
      let k = i - j
      max = Math.max(max, j * k, j * dp[k])
    }
    dp[i] = max
  }
  return dp[n]
}