14-II. 剪绳子 II
14-II. 剪绳子 II
题目
现需要将一根长为正整数 bamboo_len 的竹子砍为若干段,每段长度均为正整数。请返回每段竹子长度的最大乘积是多少。
答案需要取模 1e9+7(1000000007)
,如计算初始结果为:1000000008
,请返回 1
。
示例 1:
输入: bamboo_len = 12
输出:81
提示:
2 <= bamboo_len <= 1000
注意
本题与 LeetCode 第 343 题 相同。
解题思路
这道题和 剑指 Offer 14. 剪绳子 的思路一样,使用动态规划来解决。
但是答案需要取模 1e9+7(1000000007)
,这就需要使用 BigInt 类型来存储大整数,以避免超出 JavaScript 的整数范围。然后,最后再将结果转换回 Number 类型。
另外,BigInt 不能直接与普通的数字进行比较,所以不能使用 Math.max
方法,需要自己写一个辅助函数 max
来找到一组 BigInt 中的最大值。
解题思路如下:
定义状态: 设
dp[i]
表示整数i
拆分后的最大乘积。状态转移方程: 对于整数 i,其拆分成两个数
j
和i - j
。dp[i] 的值取决于这两个数拆分后的最大乘积,即dp[i] = max(j * (i - j), j * dp[i - j])
。需要遍历所有可能的j
来找到最大的乘积。初始状态: dp[2] = 1,因为数字 2 只能拆分成
1 + 1
,乘积为1
。计算顺序: 从小到大计算
dp
数组的值,直到计算出dp[n]
。
代码
/**
* @param {number} bamboo_len
* @return {number}
*/
var cuttingBamboo = function (bamboo_len) {
// 定义状态数组
const dp = new Array(bamboo_len + 1).fill(BigInt(0));
const MOD = BigInt(1e9 + 7);
// 初始状态
dp[2] = BigInt(1);
// 计算状态转移
for (let i = 3; i <= bamboo_len; i++) {
for (let j = 1; j < i; j++) {
dp[i] = max(dp[i], BigInt(j) * dp[i - j], BigInt(j) * BigInt(i - j));
}
}
return Number(dp[bamboo_len] % MOD);
};
var max = function (...args) {
return args.reduce((max, curr) => (curr > max ? curr : max), args[0]);
};