[343] 整数拆分

给定一个正整数 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 >= 2 的数，都可以被拆分为两个数之和，可以表示为 j 与 n - j，而剩余的 n - j 可被视作新的 n， 仍可能被继续拆分。

如果我们从小到大记录下每一个 n 的最大乘积结果，是不是就能递归解出问题的答案了。因此这其实是一道动态规划问题。

设 dp[n] 为 n 时的最大乘积结果。那么对于任意的 n，其最大乘积应为，用 j 遍历 2 ~ n ，与 n-j 的最大结果相乘，在这些结果中取最大值。

function integerBreak(n: number): number {
  const dp = Array(n + 1).fill(1);
  // 默认处理好基础情况
  // dp[1] = 1;
  // dp[2] = 1;
  for (let i = 3; i <= n; i++) {
    let temp = 0;
    for (let j = 2; j < i; j++) {
      temp = Math.max(temp, j * (i - j), j * dp[i - j]);
    }
    dp[i] = temp;
  }
  return dp[n];
}

但这样的解法并不是最优的，我们可以通过观察数学规律来进一步优化效率。

注意到任何一个数字 n，其最大乘积中一定不可能存在4及以上的数字，这是因为数字大于4时， x(x - 2) > x 恒成立，因此一定能被拆分为2与x - 2这样的数字，乘积一定比原数字大。

同时最大乘积中也不会出现1，因为拆分为1时，减小了和，却并没有增大乘积。

因此，对于所有大于4的正整数，其最大乘积拆分只可能包含2和3。

从而可以省去j遍历的复杂度。

function integerBreak(n: number): number {
  if (n < 4) return n - 1;

  const dp = Array(n + 1).fill(1);
  // 默认处理好基础情况
  // dp[1] = 1;
  // dp[2] = 1;
  for (let i = 3; i <= n; i++) {
    dp[i] = Math.max(2 * (i - 2), 2 * dp[i - 2], 3 * (i - 3), 3 * dp[i - 3]);
  }
  return dp[n];
}