LCS, DP - 9251번: LCS

dp[i][j] : s1[i - 1]과 s2[j - 1]까지 봤을 때의 최장 공통 부분 수열의 길이

1) 현재 비교하는 두 문자가 같으면 -> 이전 값(dp[i - 1][j - 1])에 + 1 해서 현재 값(dp[i][j])에 저장
dp[i][j] = dp[i - 1][j - 1] + 1
2) 다르면 -> 두 문자 중 하나는 무조건 LCS에 들어갈 수 없으므로, s1[i-1]를 버리는 경우(dp[i-1][j])와 s2[j-1]를 버리는 경우 (dp[i][j-1])를 비교하여 둘 중 더 큰 값을 선택해서 현재 값에 저장
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

s1 = input()
s2 = input()
n = len(s1)
m = len(s2)

# dp[i][j] : s1[i - 1]과 s2[j - 1]까지 봤을 때의 최장 공통 부분 수열의 길이
dp = [[0] * (m + 1) for _ in range(n + 1)]

# 문자열은 0부터 인덱스 시작하므로 -1 해줘야 함
# dp[0][0] : 아직 아무것도 안 본 상태 -> 0

# 1부터 n까지 순회
for i in range(1, n + 1):
    for j in range(1, m + 1):
        # 현재 비교하는 두 문자가 같으면
        if s1[i - 1] == s2[j - 1]:
            # 이전 값(dp[i - 1][j - 1])에 + 1 해서 현재 값(dp[i][j])에 저장
            dp[i][j] = dp[i - 1][j - 1] + 1
        # 다르면
        else:
            # 두 문자 중 하나는 무조건 LCS에 들어갈 수 없으므로, s1[i-1]를 버리는 경우(dp[i-1][j])와 s2[j-1]를 버리는 경우 (dp[i][j-1])를 비교하여
            # 둘 중 더 큰 값을 선택해서 현재 값에 저장
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

print(dp[n][m])