剪绳子

给你一根长度为 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)

评论