Dynamic算法
//longest common subsequence problem 最长公共子序列 let word = 'fosh' let anotherWord = 'fish' let answerTable = [] for(let i =0;i< anotherWord.length;i++){ let valueList = [] for(let j = 0;j< word.length;j++){ if(i===0&&j===0){ word[j]===anotherWord[i]?valueList.push(1):valueList.push(0) }else if(i===0&&j!==0){ word[j]===anotherWord[i]?valueList.push(1):valueList.push(valueList[j-1]) }else if(i!==0&&j===0){ word[j]===anotherWord[i]?valueList.push(1):valueList.push(answerTable[i-1][0]) }else{ let top = answerTable[i-1][j] let left = valueList[j-1] let value (top>left)?value = top : value = left word[j]===anotherWord[i]?valueList.push(answerTable[i-1][j-1]+1):valueList.push(value) } } answerTable.push(valueList) } console.log(answerTable,answerTable[answerTable.length-1][answerTable[answerTable.length-1].length-1])