[백준]9251 LCS #dp

1. 풀이

(1) dp[i][j] : A의 i번째, B의 j번째 문자열까지의 최장 공통 문자열의 수

(2) A[i]와 B[j]가 같다면? 왼쪽위(그전까지의 최장공통문자수)에서+1

(3) 다르다면? 위,왼쪽숫자중 최대수

​

2. 소스코드

A="0"+input()
B="0"+input()
sizeA=len(A)
sizeB=len(B)
dp=[[0 for i in range(sizeB)] for j in range(sizeA)]
for i in range(1,sizeA):
    for j in range(1,sizeB):
        if A[i]==B[j]:
            dp[i][j]=dp[i-1][j-1]+1
        else:
            dp[i][j]=max(dp[i-1][j],dp[i][j-1])
print(dp[sizeA-1][sizeB-1])