백준 9251 LCS (DP를 이용한 최장 공통 부분 수열 문제)

문제링크

문제 유형

DP

문제 풀이

dp[i][j] : 주어진 단어 s1 에 대하여 i까지, 주어진 단어 s2 에 대하여 j 까지 탐색했을 때의 최장 공통 부분 길이

계산의 편의를 위해 i=0 과 j=0 일 때의 값은 0으로 한다.
표를 채워나가며 규칙을 찾도록 한다.

표 채우기

따라서 점화식은
if(s1[i] == s2[j]) dp[i][j] = dp[i-1][j-1] + 1
else dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]