编辑代码


// Solution:https://www.jianshu.com/p/65b39734430c
// 动态规划

function cutRope(number) {
    // write code here
}

function cutRopeDP(n) {
    if(n <= 1)  return 0;
    if(n === 2) return 1;
    if(n === 3) return 2;
    
    // n >= 4
    let res = new Array(n+1).fill(0);   // 创建长度为n+1的数组并填充0
    res[0] = 0;
    res[1] = 1;
    res[2] = 2; // 剩下了一段长度为2的绳子,可以不剪
    res[3] = 3; // 剩下了一段长度为3的绳子,可以不剪

    let tmp = 0;
    for(let i=4; i<=n; i++) {
        let max = 0;
        for(let j=2; j<=Math.ceil(i/2); j++) {
            tmp = res[j] * res[i-j];
            max = tmp > max ? tmp : max;
        }
        res[i] = max;
    }

    let resStr = "";
    for(let k=1; k<=n; k++) resStr += (res[k]+", ");
    console.log(resStr);

    return res[n];
}

cutRopeDP(18);