image.png

思路

对不起一想到可以拆分k个，我就懵逼了。
核心:j (i - j) 是单纯的把整数拆分为两个数相乘，而j dp[i - j]是拆分成两个以及两个以上的个数相乘。
如果定义dp[i - j] * dp[j] 也是默认将一个数强制拆成4份以及4份以上了。

动态规划五部曲

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

dp[i]：分拆数字i，可以得到的最大乘积为dp[i]。

  1. 确定递推公式

dp[i]最大乘积是怎么得到的呢？
其实可以从1遍历j，然后有两种渠道得到dp[i].
一个是j (i - j) 直接相乘。
一个是j dp[i - j]，相当于是拆分(i - j)
核心:j (i - j) 是单纯的把整数拆分为两个数相乘，而j dp[i - j]是拆分成两个以及两个以上的个数相乘。

  1. dp的初始化

严格从dp[i]的定义来说，dp[0] dp[1] 就不应该初始化，也就是没有意义的数值。
拆分0和拆分1的最大乘积是多少？
这是无解的。
这里我只初始化dp[2] = 1，从dp[i]的定义来说，拆分数字2，得到的最大乘积是1，这个没有任何异议！

  1. var integerBreak = function(n) {
  2.     // 好聪明啊...我真想不到
  3.     let dp =new Array(n+1).fill(0) //创建空dp数组,分拆数字i，可以得到的最大乘积为dp[i]。
  4.     dp[2] =1
  6.     for(let i=3;i<=n;i++){
  7.         for(let j=1;j<i;j++){
  8.           // 这里还有循环，所以dp[i]每次都要取最大。
  9.             dp[i] =Math.max(dp[i],j*(i-j),j*dp[i-j])
  10.         }
  11.     }
  12.     return dp[n]
  14. };
  • 时间复杂度：$O(n^2)$
  • 空间复杂度：$O(n)$