整数拆分-343

[sl1673495]

给定一个正整数 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
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

这题在求解每个子问题 i 的时候，都需要另外循环一个 j，这个 j 从 1 开始把 i 拆分成 i - j。

比如 3 需要拆分成 1,2 和 2,1，4需要拆分成 1,3、2,2、3,1。

以求 max(3) 的时候为例：

1. 先考虑 1 * max(2)、 2 * max(1)

2. 还需要考虑 1 * 2、2 * 1 也就是把右侧直接作为一个值相乘，而不是拿它拆分后的最大乘积（不然这里只能求出 1 * dp[2]，也就是 1 * 1 * 1 = 1，其实是小于 1 * 2 = 2 的）。

也就是说，状态转移方程是： dp[i] = max(j * (i - j), j * dp[i - j])。

题解

let integerBreak = function (n) {
  let memo = [];
  memo[1] = 1;

  for (let i = 2; i <= n; i++) {
    let max = 0;
    // 对于每一个 i 来说，都要从 1 开始拆分成 j 和 i - j 两个正整数
    // 比如 3 需要拆分成 1,2 和 2,1 
    // 4需要拆分成 1,3、2,2、3,1
    // 然后再进一步决定最大值
    for (let j = 1; j < i; j++) {
      max = Math.max(
        max,
        // 不继续拆分 i - j,直接对比一次
        // 比如 1 和 2，不光要对比 1 * (2 拆分后的结果)
        // 也要直接对比 1 * 2
        j * (i - j),
        // 和拆分后的最大乘积相乘
        j * memo[i - j]
      );
    }
    memo[i] = max
  }

  return memo[n]
};