题目

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

方法

方法：动态规划
参考：https://blog.csdn.net/qq_25827845/article/details/73351134

动态规划

本题属于动态规划，动态规划的
动态规划的步骤：

1. 刻画一个最优解的结构特征；
2. 递归地定义最优解的值；
3. 计算最优解的值，通常采用自底向上的方法；
4. 利用计算出的信息构造一个最优解。

思路

我们定义f(n)为长度为的绳子切成若干段后的乘积的最大值
首先试图去刻画一个最优解特征，我们可以这样思考，要把长为n的绳子分为m段，肯定是一刀一刀地切割。那么，第一刀如何切，有n-1种选择。但是每种切分法，得到的乘积都可能不一样。所以f(n) = max(f(i) * f(n - i))，i有n-1种取值，1~n-1

这样我们就可以看出来，最优子结构的特征，这个公式是一个递归公式。比如n=10，那么假设第一段绳子分到4，那么就需要计算f(4)和f(6)。

得到递归公式，我们就可以自底向上计算了

注意：每个绳子切的时候，i实际上从1遍历到n/2即可，因为继续往后，切开的两段绳子组合已经和前面重复了

代码

function cutRope (number) {
  // write code here
  if (number === 2) return 1
  if (number === 3) return 2
  let fn = new Array()
  fn[1] = 1
  fn[2] = 2
  fn[3] = 3
  for (let i = 4; i <= number; i++) {
    let max = 0
    for (let j = 1; j <= i / 2; j++) {
      let mul = fn[j] * fn[i - j]
      if (mul > max) max = mul
    }
    fn[i] = max
  }
  return fn[number]
}