Envío 5542

Código

s = input()
t = input()

# well bottom up dp has never been my strong
# suit, but i think top down translates to this

n, m = len(s), len(t)
dp = [[0 for _ in range(m + 1)] for _ in range(n + 1)]

for j in range(len(t)):
    dp[len(s)][j] = len(t) - 1  

for i in range(len(s)):
    dp[i][len(t)] = len(s) - 1        

dp[len(s)][len(t)] = 0

for i in range(len(s) - 1, -1, -1):
    for j in range(len(t) - 1, -1, -1):    
        if s[i] == t[j]:    
            dp[i][j] = dp[i + 1][j + 1]
        else: 
            dp[i][j] = 1 + min(dp[i + 1][j], dp[i][j + 1], dp[i + 1][j + 1])

print(dp[0][0])