LCS 골드4 (백준, DP)

import sys
read = sys.stdin.readline

word1, word2 = read().strip(), read().strip()
l1, l2 = len(word1), len(word2)
cache = [0] * l2

for i in range(l1):
    cnt = 0
    # 새로운 값을 조회할때마다 0으로 초기화
    for j in range(l2):
        if cnt < cache[j]:
            cnt = cache[j]
        # 앞에서부터 탐색하기 때문에 캐시에 저장된 cnt 값이 0보다 큰 경우가 뒤로 갈 수록 증가하고 
        # 캐시에 저장된 값이 현재 가장 긴 문자열의 길이이기 때문에 해당 값으로 cnt를 초기화하고 1을 더해줘야한다.
        elif word1[i] == word2[j]:
            cache[j] = cnt + 1
print(max(cache))

import sys
read = sys.stdin.readline

word1, word2 = read().strip(), read().strip()
h, w = len(word1), len(word2)
cache = [[0] * (w+1) for _ in range(h+1)]

for i in range(1, h+1):
    for j in range(1, w+1):
        if word1[i-1] == word2[j-1]:
            cache[i][j] = cache[i-1][j-1] + 1
        else:
            cache[i][j] = max(cache[i][j-1], cache[i-1][j])
print(cache[-1][-1])