백준 JS 9251번 LCS. 최장 공통 부분 수열

이 문제는 위의 이미지를 참고하면 이해하기가 쉽다.

알파벳이 같다면 대각선 왼쪽의 값에서 +1, 같지 않다면 위쪽, 왼쪽에서 큰 수를 가져온다.

let fs = require('fs');
let input = fs.readFileSync('/dev/stdin').toString().trim().split("\\n")

const A = input[0].split("")
const B = input[1].split("")

const DP = Array.from({length:B.length+1}, ()=>Array(A.length+1).fill(0))

let answer = 0;
for(let i=0; i<A.length; i++){
  const a = A[i]
  for(let j=0; j<B.length; j++){
    const b = B[j]
    if(a === b){
      DP[j+1][i+1] = DP[j][i] +1
    }else {
      DP[j+1][i+1] = Math.max(DP[j][i+1], DP[j+1][i])
    }
    if(DP[j+1][i+1] > answer){
      answer = DP[j+1][i+1]
    }
  }
}
console.log(answer)