[파이썬] [DP] 백준 9251 LCS

문제

https://www.acmicpc.net/problem/9251

9251번: LCS

코드

n=list(input().rstrip())
m=list(input().rstrip())

dp=[[0]*(len(n)+1) for _ in range(len(m)+1)]

for i in range(1,len(m)+1):
    for j in range(1,len(n)+1):
        if n[j-1]==m[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])

생각 정리

CAP와 ACA를 비교할때 마지막 글자인 P와 A는 서로 다르다. 그래서 이전까지 구한 값... CAP, AC = 1 그리고 CA, ACA = 2 두가지 경우가 생긴다. 이중 최대값이 CAP와 ACA까지의 LCS가 될것이다.