剪绳子.md

note
createdAt modifiedAt tags id 2020-05-14 12:28:41 UTC 2020-05-18 14:55:46 UTC 考点/树 难度/3

剪绳子

#考点/树 #难度/3 牛客网

题目描述

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

输入描述：

输入一个数n，意义见题面。（2 <= n <= 60）

输出描述：

输出答案。

示例1

输入

8

输出

18

答案

/*
动态规划：
当前的最优解，可以从之前的最优解中找到。
假设f(n)表示长度为n的绳子的每段绳子的最大乘积，f(n)=max(f(n-i)*i),i取值范围是1~n-1
*/
function cutRope(n) {
  if (n < 2) {
    return 0;
  }
  if (n === 2) {
    return 1;
  }
  if (n === 3) {
    return 2;
  }

  let products = [0, 1, 2, 3],
    max = 0;

  for (let i = 4; i <= n; ++i) {
    max = 0; //每次重新计算最大值，虽然最大值肯定会增加，但还是需要重置
    for (let j = 1; j <= i/2; ++j) {
      const product = products[j] * products[i - j]
      if (max < product) {
        max = product;
      }
      products[i] = max;
    }
  }

  return products.pop();
}

/*
贪婪算法：
因为可以找出规律，当绳子长度大于等于5时，尽量多剪长度为3的绳子；当剩余绳子的长度为4时，把绳子剪成两端长度为2的绳子
*/
function cutRope(n) {
  if (n < 2) {
    return 0;
  }
  if (n === 2) {
    return 1;
  }
  if (n === 3) {
    return 2;
  }
  
  // 尽可能多地剪去长度为 3 的绳子段
  let timesOf3 = Math.floor(n / 3)
  
  // 当绳子最后剩下的长度为 4 的时候，不能再剪去长度为 3 的绳子段
  if (n - timesOf3 * 3 === 1) {
    timesOf3 -= 1
  }
  
  const timesOf2 = Math.floor((n - timesOf3 * 3) / 2)
  return Math.pow(3, timesOf3) * Math.pow(2, timesOf2)
}