fyhub's blog

Appearance

4.整数拆分 ​

题解 ​

js
/**
 * @param {number} n
 * @return {number}
 */
var integerBreak = function (n) {
  // 这里必须n + 1，因为索引是数值
  const dp = new Array(n + 1).fill(0);
  // 0 和 1 无法拆分
  dp[2] = 1;

  // 从3开始
  for (let i = 3; i <= n; i++) {
    for (let j = 1; j < i; j++) {
      // j * (i - j)  拆分为两个整数的乘积
      // dp[i - j] * dp[j]  拆分为多份的乘积
      dp[i] = Math.max(dp[i], j * (i - j), dp[i - j] * dp[j]);
      console.log(dp[i], j * (i - j), dp[i - j] * dp[j]);
    }
  }
  console.table(dp);
  return dp[dp.length - 1];
};
/**
 * @param {number} n
 * @return {number}
 */
var integerBreak = function (n) {
  // 这里必须n + 1，因为索引是数值
  const dp = new Array(n + 1).fill(0);
  // 0 和 1 无法拆分
  dp[2] = 1;

  // 从3开始
  for (let i = 3; i <= n; i++) {
    for (let j = 1; j < i; j++) {
      // j * (i - j)  拆分为两个整数的乘积
      // dp[i - j] * dp[j]  拆分为多份的乘积
      dp[i] = Math.max(dp[i], j * (i - j), dp[i - j] * dp[j]);
      console.log(dp[i], j * (i - j), dp[i - j] * dp[j]);
    }
  }
  console.table(dp);
  return dp[dp.length - 1];
};

思路 ​

1.确定dp数组以及下标的含义

dp[i]: 正整数i，它拆分后的整数乘积最大值。

i: 正整数i

2.确定递推公式 dp[i] = Math.max(dp[i - j] * dp[j], (i - j) * j, dp[i])

一个是j * (i - j) 直接相乘。

一个是j * dp[i - j]，相当于是拆分(i - j)

j * (i - j) 是单纯的把整数拆分为两个数相乘，而j * dp[i - j]是拆分成两个以及两个以上的个数相乘。

之所以还跟dp[i]比较，是因为要求dp[i - (1...9)]这之间的最大值，还要跟自己比

3.dp初始化

只初始化dp[2] = 1，从dp[i]的定义来说，拆分数字2，得到的最大乘积是1，这个没有任何异议

4.确定遍历顺序 dp[i] 是依靠 dp[i - j]的状态，所以遍历i一定是从前向后遍历，先有dp[i - j]再有dp[i]。

js
for (let i = 3; i <= n; i++) {
  for (let j = 1; j < i; j++) {
    // j * (i - j)  拆分为两个整数的乘积
    // dp[i - j] * dp[j]  拆分为多份的乘积
    dp[i] = Math.max(dp[i], j * (i - j), dp[i - j] * dp[j]);
    console.log(dp[i], j * (i - j), dp[i - j] * dp[j]);
  }
}
for (let i = 3; i <= n; i++) {
  for (let j = 1; j < i; j++) {
    // j * (i - j)  拆分为两个整数的乘积
    // dp[i - j] * dp[j]  拆分为多份的乘积
    dp[i] = Math.max(dp[i], j * (i - j), dp[i - j] * dp[j]);
    console.log(dp[i], j * (i - j), dp[i - j] * dp[j]);
  }
}