题目

题目来源：力扣（LeetCode）

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

示例 1:

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

示例 2:

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

思路分析

动态规划

对于的正整数 n，当 n ≥ 2 时，可以拆分成至少两个正整数的和。令 i 是拆分出的第一个正整数，则剩下的部分是 n - i ，n - i 可以不继续拆分，也可以继续拆分成至少两个正整数的和。由于每个正整数对应的最大乘积取决于比它小的正整数对应的最大乘积，因此可以使用动态规划求解。

1、状态定义
dp[i]：表示将正整数 i 拆分成至少两个正整数的和之后，这些正整数的最大乘积。

2、确定递推公式
0 不是正整数，1 是最小的正整数，0 和 1 都不能拆分，因此 dp[0] = dp[1] = 0 。

当 i ≥ 2 时，假设对正整数 i 拆分出的第一个正整数是 j (1 ≤ j < i)，则有以下两种方案：

  • 将 i 拆分成 j 和 i - j ，且 i - j 不再拆分成多个正整数，此时的乘积是 j × (i - j);
  • 将 i 拆分成 j 和 i - j ，且 i - j 继续拆分成多个正整数，此时的乘积是 j × dp[i - j];

因此，当 j 固定时，有 dp[i] = max( j × (i - j), j × dp[i - j]) 。由于 j 的取值范围是 1 到 i - 1，需要遍历所有的 j 得到 dp[i] 的最大值，因此可以得到状态转移方程如下：

dp[i] = max(dp[i], max((i - j) j, dp[i - j] j))

3、状态初始化
0 不是正整数，1 是最小的正整数，0 和 1 都不能拆分，因此初始化 dp[0] = dp[1] = 0 。但严格从dp[i]的定义来说 dp[0] dp[1] 的初始化时无意义的。

初始化dp[2] = 1，从dp[i]的定义来说，拆分数字2，得到的最大乘积是1 。

4、确定遍历顺序
确定遍历顺序，先来看看递推公式：dp[i] = max(dp[i], max((i - j) j, dp[i - j] j));
dp[i] 是依赖 dp[i - j]的状态，所以遍历 i 一定是从前向后遍历，先有 dp[i - j] 再有 dp[i] 。
枚举j的时候，是从1开始的。i是从3开始，这样dp[i - j]就是dp[2]正好可以通过我们初始化的数值求出来。
所以遍历顺序为：

  1. for (let i = 3; i <= n; i++) {
  2.   for (let j = 1; j < i - 1; j++) {
  3.     dp[i] = Math.max(dp[i], Math.max((i - j) * j, dp[i - j] * j));
  4.   }
  5. }

代码实现

  1. /**
  2.  * @param {number} n
  3.  * @return {number}
  4.  */
  5. const integerBreak = (n) => {
  6.   const dp = new Array(n + 1).fill(0);
  7.   dp[2] = 1;
  8.   for (let i = 3; i <= n; i++) {
  9.     // 对于数字 i，它可以分为两份：j 和 i-，j 的范围是 1 到 i - 1
  10.     for (let j = 1; j < i - 1; j++) {
  11.       // 对于 i-j 这部分可以拆或不拆，不拆就是 i-j，拆就是 dp[i-j]
  12.       dp[i] = Math.max(dp[i], Math.max((i - j) * j, dp[i - j] * j));
  13.     }
  14.   }
  15.   return dp[n];
  18. };

参考阅读 https://leetcode-cn.com/problems/integer-break/solution/zheng-shu-chai-fen-by-leetcode-solution/ https://leetcode-cn.com/problems/integer-break/solution/dai-ma-sui-xiang-lu-dong-tai-gui-hua-wu-r1ao3/ https://leetcode-cn.com/problems/integer-break/solution/343-zheng-shu-chai-fen-tan-xin-by-jyd/