백준 9251번(python)

---

a = [x for x in input()]
b = [x for x in input()]
alen = len(a)
blen = len(b)
dp = [[0] * (alen + 1) for _ in range(blen + 1)]

# dp[i][j] : i번째 문자와 j번째 문자 사이의 LCS길이
for i in range(1, blen + 1):
    for j in range(1, alen + 1):
    # 1 : 왼쪽값과 위쪽값, 현재까지 LCS의 최댓값을 찾기 위한 조건
    # 2 : 왼쪽 대각선 값 + 1, 과거 LCS 최댓값에 같은 문자열이므로 + 1
        dp[i][j] = max(dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1] + (a[j - 1] == b[i - 1]))
print(dp[blen][alen])

* 참조 

http://melonicedlatte.com/algorithm/2018/03/15/181550.html

[백준] 9251번 C/C++ 풀이 _ LCS - Easy is Perfect

https://reakwon.tistory.com/67

[알고리즘:DP] 백준(BOJ) 9251번 LCS