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

状态方程

• 1. dp[i][j] = dp[i - 1][j - 1] + 1; 当str1[i - 1] == str2[j - 1]
• 1. dp[i][j] = Math.max(dp[i - 1][j],dp[i][j - 1]); str1[i - 1] ！= str2[j - 1] 边界条件： dp二维数组的第0行所有元素都为0，第0列所有元素为0

let lines = [];
while (line = readline()){
    lines.push(line.trim().split(' ')) //得到字符串数组
}
let len1 = +lines[0][0];
let len2 = +lines[0][1];
let str1 = lines[1].join(' ');
let str2 = lines[2].join(' ');
let dp = new Array(len1 + 1);
for(let i = 0; i < len1 + 1; i++){
    dp[i] = new Array(len2 + 1)
}
//边界条件：
for(let i = 0; i < dp.length; i++){
    dp[i][0] = 0;
}
for(let j = 0; j < dp[0].length; j++){
    dp[0][j] = 0;
}
function findLongest (str1,str2) {
   for (let i = 1; i < dp.length; i++){
        for (let j = 1; j < dp[0].length; j++){
           
            if(str1[i - 1] == str2[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]);
            }
           
        }
    }
    console.log(dp[len1][len2])
    
}
findLongest (str1,str2)