테이블 축
행은 첫 번째 문자열, 열은 두 번째 문자열의 접두사를 뜻한다.
DP Table
LCS 2차원 DP 테이블 전이
LCS는 두 문자열을 행과 열로 놓고, 문자가 같으면 대각선, 다르면 위/왼쪽 최댓값으로 채운다.
셀 하나가 채워지는 규칙
transition문자 일치
A[i]와 B[j]가 같으면 dp[i-1][j-1] + 1을 쓴다.
문자 불일치
위쪽과 왼쪽 값 중 큰 값을 가져온다.
최종 답
오른쪽 아래 셀이 전체 LCS 길이가 된다.
문자 비교같음diag + 1다름max(up,left)
2차원 DP는 표를 채우는 방향이 중요하다. 현재 셀이 참조하는 이전 셀들이 이미 계산되어 있어야 한다.