Расстояние редактирования

За одну операцию разрешено вставить символ, удалить символ или заменить один символ на другой.

За какое наименьшее число операций первую строку можно превратить во вторую?

В первой строке первая строка, во второй — вторая. Каждая из строчных латинских букв, длина от $1$ до $1500$.

Одно число.

Три операции дают три перехода: удаление берёт значение сверху, вставка — слева, замена — по диагонали. Если символы совпали, замена не нужна и значение просто наследуется по диагонали. База — превращение в пустую строку и из пустой.