题解 | #剪绳子#

function cutRope(number)
{
    // 动态规划
    // 首先定义一个长度为 n+1 的数组 dp，其中 dp[i] 表示长度为 i 的绳子剪成若干段后的最大乘积。
    // 显然dp[2]为1，因为长度为 2 的绳子只能剪成长度为 1 的两段，乘积为 1。dp[3]显然为2.
    // 接下来，从长度为 4 开始遍历到长度为 n 的绳子，对于每个长度 i，需要找到最佳的剪法来获得最大的乘积。在长度为 i 的绳子上，可以选择剪成长度为 j 和 i-j 的两段，此时乘积为 j * (i-j)。但是，对于长度为 i-j 的绳子，可以选择继续剪，也可以不剪，因此最大乘积为 j * dp[i-j] 和 j * (i-j) 中的最大值。
    if(number === 2) return 1;
    if(number === 3) return 2;
    let dp = [0, 0, 1, 2];
    // 分别计算绳子长度大于等于4时的最大乘积
    for(let i = 4; i <= number; i++){
        // 定义保存乘积结果的数组
        let res = [];
        // 对于每个长度的绳子查找最大乘积
        for(let j = 1; j <= Math.floor(i / 2); j++){
            let product1 = j * (i - j);
            // 在j固定的情况下，显然dp[i - j]值越大，乘积越大，分解为子问题。
            let product2 = j * dp[i - j];
            res.push(Math.max(product1, product2));
        }
        dp[i] = Math.max(...res);
    }
    return dp[number];
}
module.exports = {
    cutRope : cutRope
};