Статья Автор: Дубинин Дмитрий

dp mod4 №4

a = input()
b = input()
m = []
for i in range(len(a) + 1):
    m.append(list([0] * (len(b) + 1)))
for i in range(len(a) + 1):
    m[i][0] = i
for j in range(len(b) + 1):
    m[0][j] = j
for i in range(1, len(a) + 1):
    for j in range(1, len(b) + 1):
        if a[i-1] == b[j-1]:
            m[i][j] = m[i-1][j-1]
        else:
            m[i][j] = min((m[i-1][j] + 1), (m[i][j-1] + 1), (m[i-1][j-1] + 1))
        if i >= 2 and j >= 2 and a[i-1] ==  b[j-2] and a[i-2] == b[j-1]:
            m[i][j] = min(m[i][j], (m[i-2][j-2] + 1))
print(m[-1][-1])

Чтобы оставить комментарий нужна авторизация

Печать