문자가 같음
dp[i][j] = dp[i-1][j-1] + 1
대각선 전이
LCS table
LCS는 두 접두사 축을 동시에 기억한다
dp[i][j]는 A의 i글자와 B의 j글자를 본 최장 공통 부분수열 길이다. 문자가 같으면 대각선, 다르면 위/왼쪽 중 큰 값을 고른다.
match: diag + 1
diff: max(up,left)
작은 DP 테이블
i/j0ACAY
000000
C00111
A01122
P01122
문자가 다름
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
위/왼쪽 선택초기값
한쪽 접두사가 비어 있으면 공통 부분수열 길이는 0이다.