题目描述:给你一根长度为 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。
答案需要取模 1e9+7(1000000007),如计算初始结果为:1000000008,请返回 1。
提示:2 <= n <= 1000
本题的求解思路和LeetCode 343.整数拆分几乎一样,有动态规划和贪心法两种解法,具体请看这篇文章:《LeetCode 343.整数拆分 - JavaScript》。
和 Leetcode343 不同的是,本题中的 n 的取值范围很大,需要对结果进行取模。以贪心法的思路为例,如果直接计算 n 中 3 的个数 a,然后计算 3 的 a 次方,最后再取模,那么可能会出错。
正确的做法是:利用取模运算的性质,在过程中对每一步结果取模,这样保证每一步结果都不会溢出。
代码实现如下:
// ac地址:https://leetcode-cn.com/problems/jian-sheng-zi-ii-lcof/
// 原文地址:https://xxoo521.com/2020-02-15-jian-sheng-zi-ii-lcof/
/**
* @param {number} n
* @return {number}
*/
var cuttingRope = function(n) {
if (n <= 3) return n - 1;
let res = 1;
while (n > 4) {
n -= 3;
res = (res * 3) % 1000000007;
}
return (n * res) % 1000000007;
};
时间复杂度是$O(N)$,空间复杂度是$O(1)$。