算法导论-动态规划

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 整齐打印

3.思考题15-5 编辑距离

/*
 * desc: 计算从源字符串通过有限步操作到目标字符串的最小开销
 * params: x:源字符串，y: 目标字符串，cost：复制、替换、删除、插入、交换、结束六种操作分别的代价
 */
function edit_distance(x, y, cost) {
    const m = x.length, n = y.length;
    x = " "+x;
    y = " "+y; 
    const c = [], op = [];
    let d = {}, p = 0;
    
    c.push([0]);
    op.push(['']);
    for(let i = 1; i < m+1; i++) {
        c.push([i*cost['delete']]);    //    delete;
        op.push(['delete']);
    }
    
    for(let j = 1; j < n+1; j++) {
        c[0].push(j*cost['insert']);    // insert
        op[0].push('insert');
    }
    
    if(n === 0 && cost['kill'] < c[m][0]) {
        c[m][0] = cost['kill'];
        op[m][0] = 'kill';
        p = 0;
    }
    
    for(let i = 1; i < m+1; i++) {
        for(let j = 1; j < n+1; j++) {
            d = {'copy': Infinity, 'insert': Infinity, 'replace': Infinity, 
                 'delete': Infinity, 'kill': Infinity, 'twiddle': Infinity};
            if(x[i] === y[j]) {
                d['copy'] = cost['copy'] + c[i-1][j-1];
            }
            d['replace'] = cost['replace'] + c[i-1][j-1];
            d['insert'] = cost['insert'] + c[i][j-1];
            d['delete'] = cost['delete'] + c[i-1][j];
            if(i>1 && j>1 && x[i-1] === y[j] && x[i] === y[j-1]) {
                d['twiddle'] = cost['twiddle'] + c[i-2][j-2];    
            }
            //    在两层循环尾声时候算一下kill的各种情况的成本
            if(i === m && j === n) {
                for(let k = 0; k < m; k++) {
                    if(cost['kill'] + c[k][n] < d['kill']) {
                        d['kill'] = cost['kill'] + c[k][n];
                        op[m][n] = 'kill';
                        p = k;
                    }
                }
            }
            
            c[i][j] = Infinity;
            for(let opKey in d) {
                const opC = d[opKey];
                if(opC < c[i][j]) {
                    c[i][j] = opC;
                    op[i][j] = opKey;
                }
            }
        }
    }
    
    return {c, op, p}
}

function print(x, y, op, i, j, p) {
    switch(op[i][j]) {
        case "":
            break;
        case "copy":
            print(x, y, op, i-1, j-1, p);
            console.log(`copy: ${x[i]} -> ${y[j]}`);
            break;
        case "insert":
            print(x, y, op, i, j-1,p);
            console.log(`insert:  ${y[j]}`);
            break;
        case "delete":
            print(x, y, op, i-1, j, p);
            console.log(`delete: ${x[i]}`);
            break;
        case "kill":
            print(x, y, op, p, j, p);
            console.log(`kill: ${p}`);
            break;
        case "replace":
            print(x, y, op, i-1, j-1, p);
            console.log(`replace: ${x[i]} -> ${y[j]}`);
            break;
        case "twiddle":
            print(x, y, op, i-2, j-2, p);
            console.log(`twiddle: ${x[i]} -> ${y[j-1]} ${x[i-1]} -> ${y[j]}`);
            break;
    }
}

const x = 'yydsyydssssssssssssssss', y = 'tydscs';
const cost = {'copy': 0, 'insert': 2, 'replace': 1, 'delete': 2, 'kill': 3, 'twiddle': 2};
const ret = edit_distance(x,y,cost);
print(" "+x, " "+y, ret.op, x.length, y.length, ret.p);

4.思考题15-8 基于接缝裁剪的图像压缩

/*
 * @params: A[m][n] :一个二维数组，用以标识m行n列个像素，
 *          D[m][n] :保存每个像素删除后对应的损失值
 * @return: depress[m][n]: 从第一行删除到m行的第n个像素的最小损失值
 *             op[m][n]: 对应最想损失的前一行元素的序号，-2：第一行，没有再前的行了，-1：n-1，0： n, 1: n+2
 *             q: 整体取最小值对应的最后一行的像素在的列，通过depress[m-1][q]就能得到最小损失，
 *                op[m-1][q]递归向上得最小到每一行删除的像素序号
 */

function SEAM(A, D) {
    const m = A.length, n = A[0].length;
    const depress = [], op = [];
    let q = 0, qd = Infinity;
    
    for(let i = 0; i < m; i++) {
        depress.push([]);
        op.push([])
    }
    
    for(let j = 0; j < n; j++) {
        depress[0].push(D[0][j]);
        op.push(-2);
    }
    
    for(let i = 1; i < m; i++) {
        for(let j = 0; j < n; j++) {
            let d1 =  depress[i-1][j-1] ? (D[i][j] + depress[i-1][j-1]) : Infinity;
            let d2 = D[i][j] + depress[i-1][j];
            let d3 =  depress[i-1][j+1] ? (D[i][j] + depress[i-1][j+1]) : Infinity;
            
            if(d1 < d2 && d1 < d3) {
                depress[i][j] = d1;
                op[i][j] = -1;
            } else if(d2 < d1 && d2 < d3) {
                depress[i][j] = d2;
                op[i][j] = 0;
            } else {
                depress[i][j] = d3;
                op[i][j] = 1;
            }
        }
    }
    
    for(let j = 0; j < n; j++) {
        if(qd > depress[m-1][j]) {
            q = j;    
        }
    }
    
    return {depress, op, q};
}

function print(op, i, j) {
    switch(j) {
        case -2:
            break;
        case -1:
            print(op, i-1, j-1);
            break;
        case 0:
            print(op, i-1, j);
            break;
        case 1:
            print(op, i-1, j+1);
            break;
    }
    console.log(`row: ${i} line: ${j}`);
}