题解 | #剪绳子#

function cutRope(number)
{
    // write code here
    const cache = new Array(number + 1)
    cache[0] = 0
    cache[1] = 1
    cache[2] = 2
    cache[3] = 3
    cache[4] = 4
    maxCut(number, cache)
    return cache[number]
}

function maxCut(number, cache) {
    if (cache[number]) return cache[number]
    cache[number] = 0
    // 依次尝试减去，取最大乘积
    for (let j = 2; j <= Math.floor(number / 2); j++) {
        cache[number] = Math.max(cache[number], j * maxCut(number - j, cache))
    }
    return cache[number]
}

module.exports = {
    cutRope : cutRope
};