[알고리즘] 동적 계획법(Dynamic Programming) - 백준 9251번 LCS

import sys
input = sys.stdin.readline

s1 = input().rstrip()
s2 = input().rstrip()

seq = [[0]*(len(s2) + 1) for _ in range(len(s1) + 1)]

for i in range(1, len(s1)+1):
    for j in range(1, len(s2)+1):
        if s1[i-1] == s2[j-1]:
            seq[i][j] = seq[i-1][j-1] + 1
        else:
            seq[i][j] = max(seq[i-1][j], seq[i][j-1])

print(seq[-1][-1])

LCS

LCS(Longest Common Subsequence)

LCS 는 두 문자열의 sub sequence가 같을 때, 가장 긴 길이를 구하는 문제

풀이과정

출처: https://suri78.tistory.com/11