Day26:Dynamic Programming(DP) - 动态规划(下)

Dynamic Programmin的经典应用除了斐波那契数之外，还有背包问题、最短路径问题、河内塔、LCS等等，那麽我们就试着用Dynamic Programming来解leetcode的1143题 longest common subsequence (LCS)吧!

甚麽是common subsequence?

由於common subsequence和common substring常常被搞混，因此先来理解这两者的差异吧!

common subsequence - 文字的集合出现的顺序是一样，不一定有连续性 ex abcd, abd
common substring - 连续的文字出现在两个字串里 ex ab, abc

因此LCS就是寻找出字串当中最长的common subsequence

假设现在有两个字串ANB和AKB，要求得LCS的长度的流程会如下

从字串的最後一个字开始检查
如果相同则次数+1，将相同的文字去掉後继续比较
当最後一个字不相同时，则会有两种可能性

A字串的最後一个字可能与B字串的倒数第二个字相同
B字串的最後一个字可能与A字串的倒数第二个字相同

因此拆解成两个子问题"A"与"AK"比较以及"AN"与"A"比较

4.持续的分解问题…

先试着用递回解题

const findLCS = (str1, str2) => {
    if (str1.length === 0 || str2.length === 0) return 0;
    if (str1[str1.length - 1] === str2[str2.length - 1]) {
        return (
            1 +
            findLCS(
                str1.substring(0, str1.length - 1),
                str2.substring(0, str2.length - 1)
            )
        );
    } else {
        return Math.max(
            findLCS(str1.substring(0, str1.length - 1), str2),
            findLCS(str1, str2.substring(0, str2.length - 1))
        );
    }
};

findLCS("ANB", "AKB"); //2

不过这题如果用递回解的话，leetcode执行效率会非常的差，会显示Time Limit Exceeded，如下图

使用Dynamic Programming

在用Dynamic Programming解LCS的时候，通常会用矩阵图来记录比较的结果，如下图，将比较的两个字串各自作为x轴和y轴，两两比较找出相同的字母，并且搭配箭头与数字来做标记

矩阵图的规则如下

空字串与任何单字比必定不相同，因此填入0
若两者的值不同，则比较上方和左方的格字数字大小

上方比较大标记为↑
左方比较大则标示为←
上方与左方的数字大小相同则统一标记为↑

若两者的值相同，则取左上方的值+1，并且标记为↖

依序填完数字就会发现，对角线的右下方数字即为LCS的长度，从最大的数字开始，沿着箭头的方向走，走过的格子用黄色圈圈标记，将红色箭头的所代表的字母收集起来就会得到LCS的字串，在js中习惯以二维阵列来模拟矩阵图，因此将上方的图片转化为二维阵列就会如下图

接下来试试看画出"ABCBDABC"和"BDCABAC"这两个字串的LCS矩阵图吧!

其实画到最後已经眼花撩乱

依照箭头方向收集红色的箭头就可以取得LCS为"BDABC"

用js的二维阵列来表示的话会如下图

用js实作Dynamic Programming

let table1 = []; //纪录数字
let table2 = []; //纪录箭头
let str1 = "ANB";
let str2 = "AKB";
const LCS = (str1, str2) => {
    let m = str1.length;
    let n = str2.length;
    //预先建立好格子
    for (let i = 0; i <= m; i++) {
        let arr = Array.from({ length: n }).fill(null);
        table1[i] = [0, ...arr];
    }
    table1[0].fill(0);

    for (let i = 0; i <= m; i++) {
        let arr = Array.from({ length: n + 1 }).fill(null);
        table2[i] = arr;
    }
    //放入数字和箭头
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            //由於是二维阵列的比较起始点是从1开始, 所以对应的的字串index需-1
            if (str1[i - 1] === str2[j - 1]) {
                table1[i][j] = 1 + table1[i - 1][j - 1]; //左上角的格子
                table2[i][j] = "↖";
            } else if (table1[i - 1][j] >= table1[i][j - 1]) { //上方格子大於等於左方的格子
                table1[i][j] = table1[i - 1][j];
                table2[i][j] = "↑";
            } else {
                table1[i][j] = table1[i][j - 1];
                table2[i][j] = "←";
            }
        }
    }
    console.log("table1", table1);
    console.log("table2", table2);
    return table1[m][n]; //回传LCS长度
};
let result = "";

//印出LCS字串
const printLCS = (i, j) => {
    if (i === 0 || j === 0) {
        return;
    }
    //依照箭头方向收集两个字串相同的文字
    if (table2[i][j] === "↖") {
        printLCS(i - 1, j - 1);
        result += str1[i - 1];
    } else if (table2[i][j] === "↑") {
        printLCS(i - 1, j);
    } else {
        printLCS(i, j - 1);
    }
};

LCS("ANB", "AKB"); //2
printLCS(str1.length, str2.length);
console.log("result", result); //AB

最後成功用Dynamic Programming解出longest common subsequence(LCS)了!，虽然执行时间和占用记忆体不尽理想还有待优化