题目

给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。返回你可以获得的最大乘积。
示例 1: 输入: 2输出: 1解释: 2 = 1 + 1, 1 × 1 = 1。
示例 2:输入: 10输出: 36解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。说明: 你可以假设 n 不小于 2 且不大于 58。

动态规划思路

总思路： 每个正整数对应的最大乘积取决于比它小的数对应的最大乘积

对于正整数n, 当n>=2，那么至少可以拆分成两个正整数
使k为第一个正整数 另外一个就是n-k, 那么n-k 可以继续拆分也可以不拆分

我们创建dp数组， dp[i] 表示 i 对应的最大乘积

按照上面的拆分思路

dp[i] = Math.max(k(n-k),kdp[n-k])

题解

  1. /**
  2.  * @param {number} n
  3.  * @return {number}
  4.  */
  5. var integerBreak = function(n) {
  6.     var dp = new Array(n+1)
  7.     dp[0]=dp[1]=0
  8.     for(var i= 2;i<=n;i++){
  9.         var curMax = 0 
  10.         for(var j = 1;j<i;j++){
  11.             curMax = Math.max(curMax,Math.max(j*(i-j),j*dp[i-j]))
  12.         }
  13.         dp[i]=curMax
  14.     }
  15.     return dp[n]
  16. };