[BOJ / PYTHON] 9251. LCS

A = list(input())
B = list(input())

dp = list(list(0 for _ in range(len(A) + 1)) for _ in range(len(B) + 1))

for i in range(1, len(B) + 1):
    for j in range(1, len(A) + 1):
        if A[j-1] == B[i-1]:
            dp[i][j] = dp[i-1][j-1] + 1
        else:
            dp[i][j] = max(dp[i-1][j], dp[i][j-1])

print(dp[-1][-1])

풀이.

최장 공통 부분 수열의 경우, 최장 공통 수열과 아주 비슷한 문제이다.
점화식을 통해서, A[i] 와 B[j] 가 같을 경우 DP[i-1][j-1] + 1 을 해주고, 그렇지 않다면 이전 단계(DP[i-1][j], DP[i][j-1])의 최대 값을 가져온다.