动态规划

切钢条问题

• 解法-最复杂

let priceArr = [5, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30]
let q = 0

function cut(p, n) {
    if (n === 0) {
        return 0
    }
    let i = 1
    q = p[n]
    for (let i = 1; i <= n / 2; i++) {
        q = Math.max(q, p[i] + cut(p, n - i))
    }
    return q
}
const r = cut(priceArr, 4)

• 解法-cache版本

let priceArr = [5, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30]
let q = 0
let cache = {}

function cut(p, n) {
    if (n === 0) {
        return 0
    }
    if (cache[n]) {
        return cache[n]
    }
    let i = 1
    q = p[n]
    for (let i = 1; i <= n / 2; i++) {
        q = Math.max(q, p[i] + cut(p, n - i))
    }
    if(!cache[n]){
        cache[n] = q
    }
    return q
}
const r = cut(priceArr, 4)

https://blog.csdn.net/u013309870/article/details/75193592