Динамическое программирование по шагам: вывод редакционного расстояния

Цель

Решить за полиномиальное время с предсказуемой памятью задачу, чей оптимальный ответ строится из оптимальных ответов для меньших экземпляров, а наивная рекурсия повторно вычисляет те же экземпляры экспоненциально много раз.

Предварительные условия

Два свойства: оптимальная подструктура — лучшее решение содержит лучшие решения подзадач — и перекрывающиеся подзадачи: число различных подзадач полиномиально, а наивное дерево вызовов — нет. Пример — редакционное расстояние между строками a длины m и b длины n: минимальное число вставок, удалений и замен отдельных символов, превращающих a в b.

Шаги

1. Определите состояние минимальным набором параметров, однозначно задающим подзадачу: D(i, j) — редакционное расстояние между первыми i символами a и первыми j символами b. Ответ — D(m, n).
2. Запишите базовые случаи: D(i, 0) = i — удалить всё — и D(0, j) = j — вставить всё.
3. Запишите рекуррентное соотношение. Если a[i-1] == b[j-1], то D(i, j) = D(i-1, j-1). Иначе D(i, j) = 1 + min(D(i-1, j), D(i, j-1), D(i-1, j-1)), где три варианта соответствуют удалению, вставке и замене.
4. Посчитайте состояния: (m+1) * (n+1), каждое вычисляется за постоянное время по трём соседям, поэтому алгоритм имеет сложность O(mn). Наивная рекурсия повторно посещает D(i-1, j-1) из трёх вызывающих ветвей и взрывным образом разрастается.
5. Мемоизация сверху вниз: буквально запишите соотношение рекурсивной функцией и добавьте декоратор @functools.cache, описанный в functools рядом с lru_cache. Это самый быстрый способ получить правильную версию, но глубина растёт с m + n, поэтому он подходит коротким входам.
6. Таблица снизу вверх: заполняйте её по строкам, поскольку ячейке нужны лишь строка сверху и ячейка слева. Для kitten и sitting итог — D(6, 7) = 3: заменить k на s, e на i и вставить g.
7. Сократите память: храните только предыдущую и текущую строки, получая O(min(m, n)) памяти. Если нужна сама последовательность правок, сохраните полную таблицу и пройдите назад от D(m, n).
8. Сверьте результат с полным перебором на коротких случайных строках, а также на пустых и одинаковых строках и строках с различием в один символ.

Ожидаемый результат

Функция с квадратичным временем и линейной памятью, рекуррентное соотношение которой записано в комментарии рядом с кодом, проверенная по эталону на основе полного перебора.

Ограничения и основания метода

Задачи без оптимальной подструктуры, например самый длинный простой путь в графе, этому методу не поддаются. Пространства состояний по подмножествам экспоненциальны по размеру множества и осуществимы лишь для небольших входов. Показатели примера следуют из рекуррентного соотношения арифметически; измерения времени не заявляются.