今日算法题-动态规划法

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

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

/**
 * @param {number} n
 * @return {number}
 */
var integerBreak = function(n) {
  let dp = new Array(n+1);
  dp[1] = 1;
  dp[2] = 1;
  for(let i= 3; i <= n ; i++){
    // 从小到大计算出每个dp的值
    dp[i] = 0;
    for(let j = 1; j<= i-j ; j++){  
      // j*(i-j) 不拆分i-j 
      // j*dp[i-j] 继续对i-j进行拆分,
      // dp[i-j]已经在之前的计算中计算过了，不必重复计算
      dp[i] = Math.max(dp[i], j*(i-j), j*dp[i-j])
    }
  }
  return dp[n]
};