题解 | #最长公共子序列(一)#

const rl = require("readline").createInterface({ input: process.stdin });

const inputs = [];

rl.on("line", (line) => {
    inputs.push(line);
}).on("close", () => {
    resolve(inputs);
});

function resolve(inputs) {
    const m = parseInt(inputs[0].split(" ")[0]);
    const n = parseInt(inputs[0].split(" ")[1]);
    const a = inputs[1].split(''),
        b = inputs[2].split('');
    // dp[i][j] 字符串a 和 字符串b 的最长公共子序列长度

    // if a[i] === b[j] => dp[i][j] = dp[i-1][j-1] + 1
    // else => dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    // 如果对于递推公式有疑问的，可以打表。把过程表打出来就清楚递推公式怎么来的

    // dp[0][0] = 0

    // l -> r

    const dp = Array.from(Array(m + 1), () => Array(n + 1).fill(0));
    let res = 0;
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
		  // 这里有个坑：容易写成 a[i] === b[j], 要清楚这里是字符串比较，下标是从0开始，所以应该是a[i-1] === b[j-1]
            if (a[i-1] === b[j-1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j-1]);
            }

            res = Math.max(dp[i][j], res);
        }
    }

    console.log(res);
}

步骤：

按照动归5步：

1. 明确dp数组的含义
2. 确定递推公式
3. 初始化
4. 遍历顺序
5. 打表

其实也可以通过打表来确定递推公式，从简单情况推出递推公式更简单理解一些。