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

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void (async function () {
    // Write your code here
    await readline();
    let str1 = await readline();
    let str2 = await readline();
    let dp = Array.from({ length: str1.length }, () =>
        Array.from({ length: str2.length }, () => 0)
    );

    for (let i = 0; i < str1.length; i++) {
        for (let j = 0; j < str2.length; j++) {
            if (str1[i] === str2[j]) {
			  // ab aab 第二个a不加1取上 abb ab 第二个b不加1取左
			  // 综合取左上，不包含自身元素重复元素
                dp[i][j] = (dp[i - 1]?.[j - 1] || 0) + 1;
            }
            let up = dp[i - 1]?.[j] || 0;
            let left = dp[i]?.[j - 1] || 0;
            dp[i][j] = Math.max(up, left, dp[i][j]);
        }
    }
    console.log(dp[str1.length - 1][str2.length - 1]);
})();