Запомнить, чтобы не считать

Прошлая глава кончилась на слабом месте «разделяй и властвуй». Рекурсивная fib(40) делает 331 миллион вызовов, хотя разных аргументов среди них всего 41: одни и те же подзадачи решаются снова и снова. Лекарство напрашивается — запоминать готовые ответы. Из этой мысли вырастает инструмент, которым пользуется каждый, кто набирает текст. Мы соберём две программы: одна на слово «сабака» спрашивает «Вы имели в виду: собака?», другая показывает, чем две версии текста отличаются друг от друга, как страница «Сравнение текстов» на этом сайте. Обе стоят на одном приёме со странным названием: его придумали, чтобы не рассердить министра обороны.

Заказ: опечатка

Что значит «слово похоже на другое»? Опечатки бывают трёх видов: лишняя буква, пропущенная буква, не та буква. От «сабака» до «собака» — одна замена, от «кот» до «скот» — одна вставка. Будем считать, что слово тем ближе к правильному, чем меньше таких правок нужно, чтобы его исправить. Тогда подсказка «Вы имели в виду…» — это слово из словаря, до которого правок меньше всего.

Первая мысль — перебрать все возможные правки опечатки и посмотреть, какие из получившихся строк есть в словаре. Для одной правки это работает. Посчитаем, сколько строк получается из «сабака» одной правкой и сколько — двумя.

Одна правка — 424 строки, две — уже 83 тысячи: каждая следующая правка умножает число вариантов на сотни, и три правки дали бы миллионы строк. А опечатки в длинном слове бывают и по три, и по четыре. Заходить надо с другого конца: брать каждое слово словаря и считать, сколько правок отделяет его от опечатки. Для этого нужна функция расстояния между двумя словами, причём быстрая: слов в словаре десятки тысяч. Чтобы её собрать, понадобится несколько деталей.

Деталь первая: память

Вспомним рекурсивную fib из главы 9. Она верна, но вызов fib(n) заново считает fib(n - 2), хотя тот уже был посчитан внутри fib(n - 1). Исправление — завести словарь: перед тем как считать, заглянуть в него, а посчитав, записать туда ответ.

Ответ приходит мгновенно, хотя рекурсия без памяти считала бы его дольше, чем живёт человек (мы прикидывали это в главе 13). Нажмите «Шаги»: каждое fib(k) вычисляется один раз, а все повторные вызовы сразу уходят с ответом из словаря. Разных подзадач — 89 (от fib(2) до fib(90)), на каждую одно сложение, и время из экспоненциального стало линейным.

Этот приём называют мемоизацией — от английского memo, «памятная записка»: в 1968 году британский исследователь искусственного интеллекта Дональд Мичи назвал такие функции memo-функциями. В Python её не нужно писать руками: декоратор functools.cache, о котором мы обещали рассказать в главе 10, заводит такой словарь сам, ключом служат аргументы вызова.

У памяти два условия. Функция должна быть чистой: при одних и тех же аргументах возвращать одно и то же и ничего не менять вокруг, иначе запомненный ответ однажды окажется неверным. И аргументы должны годиться в ключи словаря — числа, строки, кортежи, но не списки (почему — в главе 16).

Есть и третья трудность, менее заметная. Попробуйте в ячейке выше fib(3000): Python ответит RecursionError. Первый вызов fib(3000) ещё ничего не знает и спускается за fib(2999), тот — за fib(2998), и стек вызовов растёт на три тысячи кадров, а Python разрешает около тысячи (глава 9). Память спасла от повторов, но не от глубины. Нужен способ считать в обратную сторону, снизу вверх.

Деталь вторая: таблица

Рекурсия с памятью идёт сверху: от вопроса к подвопросам, пока не дойдёт до простых. Но можно начать сразу с простых и подниматься, заполняя таблицу ответов по порядку. Тогда к моменту, когда понадобится ответ на подзадачу, он уже будет лежать в таблице. Для Фибоначчи таблица — это список, и получается цикл, который мы уже писали в главе 9. Интереснее задача, где таблицу не так легко угадать.

На второй этаж ведёт лестница из десяти ступенек. Шагать можно на одну ступеньку вверх или сразу на две. Сколькими способами можно подняться? Будем рассуждать о последнем шаге. На десятую ступеньку можно попасть либо с девятой (шагом в одну), либо с восьмой (шагом в две). Значит, способов попасть на десятую столько, сколько на девятую, плюс столько, сколько на восьмую. И так про каждую ступеньку.

На десять ступенек — 89 способов, на сто — число из 21 цифры, и всё это за сто сложений. Перебор всех способов подняться по стоступенчатой лестнице не кончился бы никогда; таблица считает ответ, не перечисляя ни одного способа. Вы, вероятно, узнали числа: 1, 1, 2, 3, 5, 8… — это Фибоначчи под другим именем. Если разрешить шаг на три ступеньки, добавится третье слагаемое, и числа станут другими: попробуйте.

Цикл в этой программе вторичен. Вся она держится на одном предложении: ответ для ступеньки k складывается из ответов для ступенек поменьше. Такое правило называют переходом, и сочинять переходы помогает один вопрос: каким был последний шаг? Тот же вопрос выручит и на карте города.

Пути по городу

Город расчерчен улицами на квадратные кварталы. Курьеру нужно из левого верхнего перекрёстка в правый нижний, и он идёт только вправо или вниз — иначе путь не будет кратчайшим. Сколько у него разных маршрутов? Снова спросим о последнем шаге: на перекрёсток можно прийти либо сверху, либо слева. Значит, число путей до перекрёстка — сумма чисел для соседа сверху и соседа слева. На верхней улице и в левом столбце путь один: всё время прямо.

Без ремонтов числа складываются в треугольник Паскаля, повёрнутый набок. Число путей через сетку из $m$ на $n$ кварталов равно $\binom{m+n}{m}$: путь состоит из $m + n$ шагов, и надо выбрать, какие $m$ из них будут шагами вниз (в «Царице наук» эту задачу решает ладья, которая идёт домой). Но стоит перекрыть один перекрёсток, и формула перестаёт работать. Таблице всё равно: перекрытому перекрёстку она пишет ноль и считает дальше. Вот она в коде; решётка отмечает ремонт.

Порядок обхода здесь важен: строки сверху вниз, в строке — слева направо. Тогда к моменту, когда считается клетка, её сосед сверху и сосед слева уже готовы. В этом и состоит таблица снизу вверх: выбрать порядок, в котором каждая подзадача приходит после тех, от которых зависит. Для лестницы порядок — по возрастанию ступенек, для города — по строкам. Рекурсия с памятью находит такой порядок сама, ценой глубокого стека; таблица требует подумать о нём заранее, зато не упирается в глубину рекурсии и обычно работает быстрее.

RAND, 1950-е: название для министра

У приёма, собранного из двух деталей, есть имя, а у имени — одна из самых известных историй в информатике. Рассказал её сам автор названия, и мы перескажем её с его слов.

Историки замечают, что рассказ не сходится в датах. Беллман относит его к осени 1950 года, а Уилсон стал министром обороны в январе 1953-го, и статьи Беллмана со словами «динамическое программирование» выходили ещё до этого. Может быть, память сдвинула события, а может быть, история отшлифовалась за годы пересказов. Как бы то ни было, название прижилось. Динамическое программирование — способ решать задачи, которые сводятся к подзадачам поменьше, причём одни и те же подзадачи встречаются много раз: каждую решают один раз и запоминают ответ, сверху (рекурсией с памятью) или снизу (таблицей).

От «разделяй и властвуй» из прошлой главы его отличает только этот повтор. Слияние делит список на непересекающиеся половинки, и запоминать там нечего: каждая половинка встречается один раз. У лестницы и города подзадачи перекрываются: ответ для перекрёстка нужен и его правому соседу, и нижнему. Где подзадач немного, а повторов много, динамическое программирование и выигрывает.

Деталь третья: касса

Теперь задача, где легко ошибиться, даже зная приём. Сколькими способами можно набрать 5 тенге монетами в 1, 2 и 5 тенге? Рассуждение «по последнему шагу» подсказывает переход: последней монетой могла быть единица, двойка или пятёрка, значит, ways[s] = ways[s - 1] + ways[s - 2] + ways[s - 5]. Посчитаем — и сравним с ответом, полученным другим способом.

Девять против четырёх. Выпишем руками: 5; 2 + 2 + 1; 2 + 1 + 1 + 1; 1 + 1 + 1 + 1 + 1 — четыре способа. Первая функция насчитала больше, потому что считает последовательности: для неё 2 + 2 + 1, 2 + 1 + 2 и 1 + 2 + 2 — три разных способа, ведь порядок монет у них разный. Для лестницы это было правильно — порядок шагов там важен, — а для кошелька нет.

Вторая функция устроена хитрее: сначала считает способы только из единиц, потом разрешает двойки, потом пятёрки. Монеты добавляются по видам, и каждый набор считается ровно один раз — в порядке «сначала все единицы, потом все двойки». Переход должен в точности описывать, что мы считаем разным. Сто тенге монетами в 1, 2, 5 и 10 тенге можно набрать 2156 способами; первая функция насчитала бы около $1{,}2 \cdot 10^{23}$.

Кассиру, впрочем, нужен один способ — самый короткий: дать сдачу наименьшим числом монет. Это задача на оптимум, и переход меняется: вместо суммы — минимум. Если последняя монета в лучшей сдаче — $c$, то до неё должна стоять лучшая сдача суммы $s - c$. Перебираем все варианты последней монеты и берём лучший:

$$\mathit{best}(s) = 1 + \min_{c \le s} \mathit{best}(s - c), \qquad \mathit{best}(0) = 0.$$

Кроме самой таблицы best программа хранит вторую, last: какой выбор дал лучший ответ. По ней ответ восстанавливается в обратную сторону — от суммы к нулю, по монете за шаг. Это общий приём: таблица чисел говорит, сколько, а таблица выборов — как. Без неё мы бы знали, что 88 тенге сдаются одиннадцатью монетами, но не знали какими. Интереснее 13 тенге двушками и пятёрками: две пятёрки дали бы сдачу короче, но остаток в 3 тенге двушками не набрать, и таблица находит 2 + 2 + 2 + 2 + 5. А 3 тенге такими монетами не набрать вовсе.

Остаётся понять, почему минимум из лучших сдач для меньших сумм даёт лучшую сдачу для большей. Пусть в лучшей сдаче суммы $s$ последняя монета — $c$. Остальные монеты дают $s - c$. Если бы сумму $s - c$ можно было набрать меньшим числом монет, мы бы заменили ими остальные и получили сдачу суммы $s$ лучше лучшей — противоречие. Значит, внутри оптимального решения сидят оптимальные решения подзадач. Это свойство называют оптимальной подструктурой, и именно оно разрешает собирать оптимум из оптимумов. Без него таблица лучших ответов бесполезна. Например, самый длинный путь без повторов в графе так не найти: продолжение длинного пути может упереться в вершины, уже занятые его началом.

Деталь четвёртая: рюкзак

В лавку древностей ночью забрался вор. В рюкзак помещается 10 килограммов, а на полках — самовар, часы, картина и ещё пять вещей, у каждой свой вес и цена. Что унести, чтобы взять подороже? Попробуйте сами, прежде чем читать дальше.

Эта задача отличается от кассы. Монет каждого вида сколько угодно, а самовар один: взяв его, второй раз не возьмёшь. Поэтому одной суммы в подзадаче мало, нужно помнить и то, какие вещи уже рассмотрены. Расставим вещи в ряд и решим, начиная с первой, брать каждую или нет. Подзадача — пара чисел: «лучшая добыча из первых $i$ вещей при вместимости $w$». Для $i$-й вещи с весом $m_i$ и ценой $p_i$ вариантов два: не брать её, и тогда ответ тот же, что для $i - 1$ вещей, или взять, если влезает, и тогда к её цене прибавляется лучшая добыча из первых $i - 1$ вещей в оставшиеся $w - m_i$ килограммов:

$$\mathit{best}(i, w) = \max\bigl(\mathit{best}(i-1, w),\; p_i + \mathit{best}(i-1, w - m_i)\bigr).$$

Самое дорогое — самовар — в лучший рюкзак не попадает, и «сначала самое дорогое» здесь проигрывает: самовар с часами дают 50, а картина, статуэтка, книга и шкатулка — 54. Восстановление снова идёт с конца: если ответ в клетке $(i, w)$ отличается от ответа без $i$-й вещи, значит, вещь взята, и вместимость уменьшается на её вес.

Таблица здесь — $n + 1$ строк на $W + 1$ столбцов, работа — порядка $n \cdot W$. На восьми вещах и десяти килограммах это 99 клеток против $2^8 = 256$ наборов перебора, а на сотне вещей перебор уже безнадёжен: $2^{100}$ наборов. Но есть подвох: укажите веса в граммах, и столбцов станет в тысячу раз больше, хотя задача та же. Время зависит от величины чисел во входе, а не только от их количества, и для весов с двадцатью знаками таблица не поможет. Есть ли для рюкзака способ, быстрый при любых весах, не знает никто: это одна из задач, о которых пойдёт речь в главе 57.

Деталь пятая: подпоследовательность

Для сравнения текстов понадобится ещё одно понятие. Из строки «колобок» можно вычеркнуть буквы и получить «клок» или «обок»: оставшиеся буквы идут в том же порядке, что и были, но не обязательно подряд. Такой результат вычёркивания называют подпоследовательностью. Подстрока из главы 7 — частный случай, когда вычеркнуть можно только с краёв.

Разомнёмся на классической задаче: найти в ряду чисел самую длинную возрастающую подпоследовательность. Например, в цифрах числа $\pi$. Подзадача: «длина самой длинной возрастающей подпоследовательности, которая кончается на элементе $i$». Переход: такая подпоследовательность — это элемент $i$, приставленный к лучшей подпоследовательности, которая кончается на каком-нибудь меньшем элементе левее. Ответ — лучшая из всех.

Двойной цикл — порядка $n^2$ шагов. Есть способ быстрее, и в нём работает двоичный поиск из главы 20. Будем хранить список tails: tails[k] — наименьший последний элемент, каким может кончаться возрастающая подпоследовательность длины $k + 1$. Этот список всегда возрастает, и каждое новое число либо удлиняет его, либо уменьшает один из хвостов — тот, место которого находит bisect_left. Получается $n \log n$.

В случайной перестановке $n$ чисел самая длинная возрастающая подпоследовательность оказывается чуть короче $2\sqrt{n}$. Вопрос об этой длине задал Станислав Улам в 1961 году, а в 1977-м Анатолий Вершик и Сергей Керов доказали, что она растёт как $2\sqrt{n}$; оценку снизу одновременно с ними и независимо получили Бенджамин Логан и Лоуренс Шепп. Но нам подпоследовательности нужны для другого: на их языке говорит сравнение текстов. Вернёмся к нему через одну деталь.

Деталь шестая: расстояние между словами

Расстояние редактирования, или расстояние Левенштейна, и есть мера для опечаток, которую мы искали. Подзадача — расстояние между началами слов: первыми $i$ буквами слова $a$ и первыми $j$ буквами слова $b$. И снова вопрос о последнем шаге: что стало с последней буквой? Вариантов три.

• Последнюю букву $a$ удалили: остаётся превратить первые $i - 1$ букв $a$ в первые $j$ букв $b$, плюс одна правка.
• В конец вставили последнюю букву $b$: остаётся превратить $i$ букв $a$ в $j - 1$ букву $b$, плюс одна правка.
• Последнюю букву $a$ превратили в последнюю букву $b$: бесплатно, если они совпадают, иначе это замена, одна правка. Остаётся $i - 1$ и $j - 1$.

$$d(i, j) = \min\bigl(d(i-1, j) + 1,\; d(i, j-1) + 1,\; d(i-1, j-1) + [a_i \ne b_j]\bigr), \qquad d(i, 0) = i,\; d(0, j) = j.$$

Квадратные скобки означают единицу, если буквы разные, и ноль, если одинаковые. С краями таблицы всё ясно: пустое начало превращается в $j$ букв $j$ вставками, а $i$ букв в пустоту — $i$ удалениями. Сначала запишем формулу рекурсией в лоб и посчитаем вызовы, потом добавим одну строку с cache.

Больше шестисот тысяч вызовов против 88. Разных подзадач здесь столько, сколько пар «начало первого слова, начало второго»: $11 \cdot 8 = 88$, а рекурсия без памяти обходит их сотни тысяч раз. Таблицу удобнее всего заполнять так же, как город курьера, строка за строкой. Она и есть такой город. Поставьте буквы первого слова вдоль левого края, второго — вдоль верхнего. Шаг вниз — удалить букву, шаг вправо — вставить, шаг по диагонали — оставить букву (бесплатно) или заменить (одна правка). Каждый способ превратить одно слово в другое — путь из левого верхнего угла в правый нижний, а расстояние — цена самого дешёвого пути.

Восстановление здесь такое же, как в кассе и рюкзаке: идём из правого нижнего угла назад и каждый раз спрашиваем, из какого соседа клетка получила своё значение. Путь назад и есть рецепт правок, только задом наперёд. Таблица занимает $(m + 1)(n + 1)$ клеток, на каждую — три сравнения, поэтому время — порядка $m \cdot n$. Для расстояния, без самих правок, всю таблицу хранить не нужно: каждая строка зависит только от предыдущей. Вот рабочая функция, которой мы будем пользоваться дальше.

Сборка: «Вы имели в виду…»

Деталей хватает. Словарь возьмём из «Войны и мира»: все слова романа, нарезанные функцией words из главы 7, и сколько раз каждое встречается, — Counter из главы 8. Французские фразы романа отбросим: оставим слова только из русских букв. Для опечатки посчитаем расстояние до каждого слова словаря и оставим ближайшие. Если ближайших несколько, первым предложим самое частое — оно вероятнее. И одна экономия: слова, длина которых отличается от длины опечатки больше чем на два, ближе двух правок быть не могут, их можно не сравнивать.

Попробуйте «сабака», «масква», «напалеон», «наташя» — программа справляется, на каждое слово уходит доля секунды. С «превет» хуже: программа предложит «прервет». Ошибки в коде нет: в «Войне и мире» ни разу не встречается слово «привет», а программа знает только свой словарь. «Карова» превратится в «какова»: оба слова на одну правку от опечатки, но «какова» в романе встречается чаще коровы. Человек сразу видит, что «а» вместо «о» — частая ошибка, а «р» вместо «к» — редкая; программа считает все правки одинаковыми. И «кампьютер» станет «камергером»: в словаре 1869 года компьютеров нет, а ближайшее слово отстоит на четыре правки, и подсказка уже бессмысленна.

Настоящие проверки орфографии опираются на ту же меру, только с поправками на эти три беды. Словарь у них большой и современный. Правки весят по-разному: замена соседних клавиш или безударных гласных стоит дешевле, чем замена далёких букв. Четвёртым видом правки считают перестановку двух соседних букв — «кмоар». Его ввёл Фред Дамерау в 1964 году: по его подсчётам, больше 80 % опечаток — одна вставка, одно удаление, одна замена или одна перестановка. И подсказки дальше двух правок обычно не предлагают вовсе. Всё это поправки к переходу, а таблица остаётся той же.

Сборка: что изменилось

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

$$L(i, j) = \begin{cases} L(i-1, j-1) + 1, & a_i = b_j, \\ \max\bigl(L(i-1, j),\, L(i, j-1)\bigr), & a_i \ne b_j. \end{cases}$$

Это родственник расстояния Левенштейна: если запретить замены и разрешить только вставки и удаления, расстояние между строками длины $m$ и $n$ будет ровно $m + n - 2L(m, n)$. Сравнивать можно буквы, слова или целые строки: таблице всё равно, что сравнивать, лишь бы элементы можно было проверить на равенство. Программы сравнения текстов обычно сравнивают строки.

Так устроено ядро программы diff. Она появилась в Unix в 1974 году, а в 1976-м её авторы Джеймс Хант и Дуглас Макилрой из Bell Labs описали свой алгоритм: он ищет ту же общую подпоследовательность строк, но экономнее полной таблицы. Экономия нужна: два файла по сто тысяч строк дали бы таблицу в десять миллиардов клеток. В 1986 году Юджин Майерс нашёл алгоритм, время которого зависит от размера файлов, умноженного на число различий. Версии файлов обычно отличаются немногим, и он работает почти линейно. Его по умолчанию использует git; на нём же построена библиотека diff-match-patch, а на ней работает страница сравнения текстов этого сайта. Есть в git и режим --patience: он сначала находит строки, которые в каждой версии встречаются только один раз, и выстраивает их наибольшей возрастающей подпоследовательностью из пятой детали.

Как узнать динамику

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

1. Что за подзадача? Обычно это начало входа: первые $k$ ступенек, первые $i$ вещей, первые $i$ букв одного слова и $j$ другого. Подзадача должна помнить всё, что нужно для решения, — у рюкзака одной суммы было мало.
2. Какой переход? Спросите, каким был последний шаг, и переберите все варианты: последняя монета, брать вещь или нет, что стало с последней буквой.
3. Где база? Самые маленькие подзадачи, ответ на которые очевиден: ноль ступенек, пустое слово.
4. В каком порядке заполнять? Так, чтобы каждая клетка считалась после тех, от которых зависит. Или доверить порядок рекурсии с @cache, если стек выдержит её глубину.
5. Как восстановить ответ? Запомнить выбор в каждой клетке или пройти от угла назад, спрашивая, откуда пришло значение.

Время работы — число подзадач, умноженное на число вариантов в переходе. У лестницы $n$ подзадач по два варианта, у Левенштейна $m \cdot n$ подзадач по три, у рюкзака $n \cdot W$ по два. Рецепт не сработает, если подзадачи не повторяются (тогда хватит «разделяй и властвуй»), если нет оптимальной подструктуры (как у самого длинного пути без повторов) или если подзадач слишком много: у задачи коммивояжёра из главы 58 их число растёт как $n \cdot 2^n$.

В задаче «самая длинная возрастающая подпоследовательность» подзадачей было «лучшая длина, которая кончается на элементе $i$», а не «лучшая длина среди первых $i$ элементов». Зачем такая странная подзадача?

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

Про лучшую подпоследовательность среди первых $i$ элементов известна только длина, а чтобы приставить к ней новое число, надо знать, на чём она кончается. Подзадача «с концом в $i$» как раз это и хранит. Если переход не получается, часто помогает уточнить подзадачу.

Задачи

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

Напишите stairs(n, steps, broken) — сколькими способами можно подняться с земли (ступенька 0) на ступеньку n, если за один шаг разрешено подняться на любое число ступенек из списка steps, а на ступеньки из множества broken наступать нельзя. Порядок шагов важен: 1 + 2 и 2 + 1 — разные способы. Если n сама гнилая, способов ноль; при n = 0 способ один — стоять на месте. Ступенек бывает до десяти тысяч, ответ — большое целое число.

Возьмите stairs из главы. Что меняется, если ступенька k гнилая? На неё нельзя попасть ни одним способом — значит, ways[k] = 0, и дальше по таблице этот ноль сам сделает своё дело.

Последний шаг на ступеньку k мог быть любым s из steps, если s <= k. Сложите ways[k - s] по всем таким шагам.

Если broken передали списком, проверка k in broken будет медленной на длинной лестнице; надёжнее в начале сделать broken = set(broken). Время — $n$, умноженное на число разрешённых шагов.

В кассе монет не бесконечно много: stock — словарь «номинал → сколько таких монет есть», например {10: 2, 5: 1, 2: 3, 1: 0}. Напишите min_coins(total, stock): список монет, которыми можно выдать ровно total, наименьший по длине, или None, если выдать нельзя. Если лучших вариантов несколько, годится любой. Сумм бывает до 2000, видов монет — до десяти, монет каждого вида — до сотни.

Таблица best[s] из главы считала, что монет каждого вида сколько угодно. Здесь каждая монета — как вещь в рюкзаке: её можно взять один раз. Разложите запас на отдельные монеты и добавляйте их по одной.

Если обходить суммы при добавлении монеты по возрастанию, одна и та же монета попадёт в сдачу дважды: best[s - c] уже может её содержать. Обходите суммы по убыванию, от total до c, — так best[s - c] ещё не знает о новой монете. Для восстановления храните рядом список монет для каждой суммы или «какой монетой улучшили».

Обход по убыванию — та же мысль, что строка best[i - 1] в рюкзаке: при добавлении новой монеты мы опираемся на таблицу без неё. Списки used копируются, это лишняя работа; экономнее хранить в каждой сумме только последнюю монету и счётчики, но на таких размерах хватает и простого способа. Время — сумма, умноженная на общее число монет: до двух миллионов шагов.

Добавьте к расстоянию Левенштейна четвёртую правку — перестановку двух соседних букв, как предлагал Дамерау: «кмоар» → «комар» — одна правка, а не две. Напишите damerau(a, b). Переставленные буквы дальше не трогаются: правило такое — если последние две буквы начала a совпадают с последними двумя буквами начала b, но в обратном порядке, к трём вариантам перехода добавляется четвёртый: $d(i-2, j-2) + 1$. Строки бывают длиной до тысячи символов.

Возьмите таблицу d размером $(m + 1) \times (n + 1)$ с краями d[i][0] = i и d[0][j] = j и заполните её, как в главе. Новый вариант проверяйте только при i >= 2 и j >= 2.

Условие перестановки на языке индексов: a[i - 1] == b[j - 2] и a[i - 2] == b[j - 1]. Двух строк таблицы здесь мало: переход заглядывает на две строки назад, так что проще хранить всю таблицу.

Это так называемое ограниченное расстояние Дамерау — Левенштейна: переставленную пару больше не правят. Из-за этого ограничения оно не всегда удовлетворяет неравенству треугольника: от «ca» до «abc» оно насчитает три правки, хотя через «ac» хватает двух. Полная версия без ограничения устроена сложнее; для проверки орфографии обычно хватает этой.

Напишите lcs(a, b), которая возвращает саму наибольшую общую подпоследовательность двух строк — строку, а не её длину. Если таких несколько, годится любая. Тесты проверят, что ответ — подпоследовательность обеих строк и что длиннее не бывает. Строки — до полутора тысяч символов.

Заполните таблицу длин L, как в программе diff из главы. Потом идите из угла (m, n) назад: если буквы совпадают — берите букву и шагайте по диагонали, иначе шагайте туда, где число больше.

Буквы при движении назад собираются с конца. Сложите их в список и разверните в конце, а не приписывайте к началу строки: это квадратичная работа.

Шагая туда, где число больше, мы не теряем ответ: если буквы разные, по переходу $L(i, j)$ равно большему из соседей, и оптимальная подпоследовательность есть в той подзадаче, откуда взялось это значение.

Напишите loot(items, capacity): items — список троек (название, вес, цена) с целыми неотрицательными весами и ценами, названия разные. Функция возвращает список названий вещей, которые надо взять, чтобы суммарный вес не превысил capacity, а суммарная цена была наибольшей. Если лучших наборов несколько, годится любой. Вещей бывает до ста, вместимость — до десяти тысяч.

Таблица best[i][w] — лучшая добыча из первых i вещей при вместимости w, как в главе. Сто вещей на десять тысяч килограммов — миллион клеток, это по силам.

Восстановление: идите по вещам с конца. Если best[i][w] != best[i - 1][w], вещь i взята — вычтите её вес из w. Вещи с нулевым весом не ломают этот способ: если такая вещь что-то стоит, ответ из-за неё изменится.

Строки prev и row — короткие имена для двух строк таблицы: так во внутреннем цикле меньше индексации. Если нужна только цена, хватит одной строки, которую обходят по убыванию веса, — тот же приём, что в кассе с пустыми ячейками. Но тогда восстановить набор уже не получится.

Куда дальше

Проверка орфографии и сравнение версий собраны из одних и тех же деталей. Вернёмся напоследок к кассе. Таблица находит самую короткую сдачу для любой суммы и любого набора монет, но для этого перебирает все суммы от нуля до нужной и все монеты для каждой. Живой кассир таблиц не заполняет. Он берёт самую крупную монету, которая помещается в сдачу, потом снова самую крупную — и с монетами тенге почему-то всегда получает наименьшее число монет. Такой шаг, лучший прямо сейчас, без оглядки на будущее, называют жадным. Когда жадность приводит к лучшему ответу, а когда заводит в тупик, из которого уже не выбраться, — об этом следующая глава, где жадность проведёт электричество в моравские деревни.