一、题目内容 中等

给定一个正整数 n ，将其拆分为 k 个 正整数 的和（ k >= 2 ），并使这些整数的乘积最大化。
返回 你可以获得的最大乘积 。

示例1：

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

示例2：

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

提示:

  • 2 <= n <= 58

    二、解题思路

    题目给定一个正整数 n，我们把它拆分成 k 个数，又不确定几个。我们利用化归的思路，从最小的数开始找规律。
    如果 n = 2，找 1 x (2 - 1)，取最大 1
    如果 n = 3，找 1 x (3 - 1)，取最大 2
    如果 n = 4，找 1 x (4 - 1)，找 2 x (4 - 2)，取最大 4
    如果 n = 5，找 1 x (5 - 1)，找 2 x (5 - 2)，取最大 6
    如果 n = 6，找 1 x (6 - 1)，找 2 x (6 - 2)，找 3 x (6 - 3)，取最大 9
    以此类推。
    可是这样又只是分了两个数，而且其实每次都是找 n + 1 ，那如果我能利用 n 的结果，不是更好吗？
    这样需要比较 n * (n + 1 - n)、(n - 1) * (n + 1 - (n -1))、...、1 * (n + 1 - 1)
    和 n * dp[n + 1 - n]、(n - 1) * dp[n + 1 - (n - 1)]、...、1 * dp[n + 1 - 1]

其中 i * dp[n + 1 - i]，意味着从 n 取出正整数 i，剩下的dp[n + 1 - i]是之前 n + 1 - i这个数拆分后的最大值，我们每次都是利用之前的最大值。
取最大的最大，最后肯定是最大的值。

所以采用动态规划来做。

  1. 令 i 为 0 ~ n ，dp[i] 表示正整数 i 的拆分整数后的最大乘积
  2. 递推公式：dp[i] = max{j * (i - j), j * dp[i - j]}，其中j表示 i 拆分的第一个整数
  3. 初始化 dp[0] = 1、dp[1] = 1

三、具体代码

  1. /**
  2.  * @param {number} n
  3.  * @return {number}
  4.  */
  5. var integerBreak = function (n) {
  6.   const dp = [1, 1]; // 初始化 n = 0 和 n = 1 时的最大乘积
  7.   for (let i = 2; i <= n; i++) {
  8.     let sum = 0;
  9.     for (let j = i - 1; j > 0; j--) {
  10.       sum = Math.max(sum, j * (i - j), j * dp[i - j]);
  11.     }
  12.     dp[i] = sum;
  13.   }
  14.   return dp[n];
  15. };
  16. /**
  17.  * 时间复杂度：O(n^2)
  18.  * 空间复杂度：O(n)
  19.  */

四、其他解法