LCS (Longest Common Subsequence)

참고 : https://www.youtube.com/watch?v=EAXDUxVYquY

코드

word_a = input()
word_b = input()
dp = [[0 for _ in range(len(word_a) + 1)] for _ in range(len(word_b) + 1)]

for i in range(len(word_b)):
    for j in range(len(word_a)):
        if word_b[i] == word_a[j]:
            dp[i + 1][j + 1] = dp[i][j] + 1
        else:
            dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1])
print(dp[len(word_b)][len(word_a)])

접근방식

하나씩 규칙성을 찾아 점화식을 구하는 것 보다
대략적인 점화식을 만들고 다듬어가는게 더 수월할 듯?