剪绳子

给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]...k[m-1] 。请问 k[0]*k[1]*...*k[m-1] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。


示例 :

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


解法：贪心算法

经过数学推导可得，尽可能将绳子分成长度为3时，乘积最大。所以，划分规则如下：

1. 最优的情况：将绳子尽可能切为多个长度为 33 的片段。

2. 次优的情况：若最后一段绳子长度为 2 ；则保留，不再拆为 1+1 。

3. 最差的情况：若最后一段绳子长度为 1 ；则应把一份 3+1 替换为 2+2，因为 2*2 > 3*1。


/**
 * @param {number} n
 * @return {number}
 */
let cuttingRope = function(n) {
  if (n===2) return 1;
  if (n===3) return 2;
  let a = Math.floor(n / 3), b = n % 3;
  switch (b) {
    case 0:  // 最优的情况
      return Math.pow(3, a);
    case 1:  // 最差的情况
      return Math.pow(3, a - 1) * 2 * 2;
    case 2:  // 次优的情况
      return Math.pow(3, a) * 2;
  }
};


评论(0)

评论