文章目录

我的网站

题目

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

答案需要取模 1e9+7 (1000000007) , 如计算初始结果为: 1000000008, 请返回 1.

示例 1:

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

示例 2:

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

提示: 2 <= n <= 1000

链接：https://leetcode-cn.com/problems/jian-sheng-zi-ii-lcof

题解

这道题和前一题差不多, 区别就在于绳子的最大长度

然后还有最后取模

可以直接使用 JS BigInt 解决

需要注意的是: BigInt 只能和 BIgInt 相互计算不能和普通数字一起计算

var cuttingRope = function (n) {
  const fixedLength = [0, 0, 1, 2, 4];
  if (n <= 4) return fixedLength[n];

  let map = [0, 1, 1, 2, 4];
  for (let i = 5; i <= n; i++) {
    const res = BigInt(3) * (i - 3 <= 4 ? BigInt(i - 3) : map[i - 3]);
    map.push(BigInt(res));
  }

  map = map.map((e) => BigInt(e) % BigInt(1000000007));

  return map[n];
};

// cuttingRope(120);