Автозамена в телефоне

Ты печатаешь сообщение в телефоне, а автозамена пытается понять, что ты имел(а) в виду. Телефон умеет исправлять текст тремя типами правок:

• вставить один символ,
• удалить один символ,
• заменить один символ на другой.

Каждая правка стоит 1.

Нужно узнать, сколько правок минимально нужно, чтобы превратить набранную строку в желаемую.

Формат ввода

Даны две строки s и t, каждая в отдельной строке.

Формат вывода

Выведите одно число — минимальную стоимость превращения строки s в строку t.

Ограничения

• 1 ≤ |s| ≤ 400
• 1 ≤ |t| ≤ 400
• строки состоят только из строчных латинских букв a..z
• время: 2 секунды, память: 256 МБ

Пример

Ввод:

kitten
sitting

Вывод:

3

Пояснение к примеру: kitten → sitten (замена k на s), sitten → sittin (замена e на i), sittin → sitting (вставка g).

Ключевое наблюдение: любые правки превращают строку шаг за шагом, и в конце важно только то, какие префиксы уже приведены друг к другу. Поэтому можно считать ответ для s[:i] и t[:j], а потом наращивать.

Введём dp[i][j] — минимальное число правок, чтобы превратить первые i символов s в первые j символов t. Почему ДП работает: последний шаг в оптимальном преобразовании обязательно один из трёх типов правок, и он переводит нас в одну из «соседних» клеток таблицы.

Переходы (последняя операция):

• удалить s[i-1]: dp[i-1][j] + 1
• вставить t[j-1]: dp[i][j-1] + 1
• заменить s[i-1] на t[j-1] (или оставить, если равны): dp[i-1][j-1] + (0 или 1)

Минимум из них и есть dp[i][j].

План решения:

• Пусть m=len(s), n=len(t).
• Инициализируй базу: dp[0][j]=j (вставить j символов), dp[i][0]=i (удалить i символов).
• Для i=1..m и j=1..n посчитай dp[i][j] по трём вариантам выше.
• Ответ — dp[m][n].

Сложность: O(m*n) по времени, при ограничениях 400 это быстро. Память можно сделать O(n), храня только две строки таблицы.

Частая ошибка: перепутать индексы (s[i-1], t[j-1]) и базу dp[0][j], из-за этого ответы «съезжают» на 1.