算法导论-动态规划

来源：恒创科技编辑：恒创科技编辑部

2024-01-25 18:37:59

1.思考题15-2 最长回文子序列

let a = "Hello World!";

function LCA(arr) {
    let n = arr.length, ret = [], w = [];
    
    for(let i = 0; i < n; i++) {
        ret.push([]);
        w.push([]);
    }
    for(let i = 0; i < n; i++) {
        ret[i][i] = 1;
        w[i][i] = a[i];
    }
    
    for(let l=2; l < n+1; l++) {
        for(let i = 0; i < n-1 && i+l-1<n; i++) {
            let j = i+l-1;
            if(a[i] == a[j]) {
                ret[i][j] = ret[i+1][j-1] + 2;
                w[i][j] = a[i] + w[i+1][j-1] + a[j];
            } else if(ret[i+1][j] > ret[i][j-1]) {
                ret[i][j] = ret[i+1][j];
                w[i][j] = w[i+1][j];
            } else {
                ret[i][j] = ret[i][j-1];
                w[i][j] = w[i][j-1];
            }
        }
    }
    
    return {ret,w};
}

let {ret,w} = LCA(a.split(''));
console.log(ret[0][11])
console.log(w)

2.思考题15-4 整齐打印