Динамическое программирование на примере размена монет
Кассир хочет дать сдачу как можно меньшим числом монет — а компьютер хочет того же, но не угадывая. Разменяй монеты грамотно, и ты на самом деле освоишь динамическое программирование — приём, на котором держатся маршруты в навигаторе и проверка орфографии.
Представь: ты кассир, в чеке сдача 11 рублей, а в кассе монеты по 1, 2 и 5. Как набрать сумму наименьшим числом монет? Кажется, можно просто хватать самую крупную — но именно тут прячется ловушка, в которую попадают даже взрослые. А выберется из неё приём с громким именем: динамическое программирование.
Жадность, которая подводит
Первая мысль почти у каждого одинаковая: бери монеты покрупнее. Нужно набрать 11 рублей монетами 1, 2 и 5 — берём 5, ещё 5, остаётся 1, берём единицу. Три монеты, отлично. Этот подход называется жадным: на каждом шаге хватаем самое выгодное прямо сейчас, не заглядывая вперёд.
Беда в том, что жадность не всегда права. Поменяем набор монет на 1, 3 и 4 и попробуем набрать 6. Жадный кассир схватит самую крупную — 4, останется 2, и её придётся добивать двумя единицами: 4 + 1 + 1, итого три монеты. А ведь можно было взять 3 + 3 — и обойтись двумя. Жадность промахнулась, потому что выгодный сейчас шаг закрыл дорогу к лучшему решению потом.
Главная мысль динамического программирования: чтобы решить большую задачу, реши такие же задачи поменьше и собери ответ из них.
Разбиваем задачу на кусочки поменьше
Давай рассуждать иначе. Обозначим за min(N) минимальное число монет, которым можно набрать сумму N. Какой бы ни была последняя монета, после неё остаётся сумма поменьше, которую тоже надо набрать оптимально. Значит, чтобы получить N, мы перебираем все монеты и смотрим, что выгоднее.
Для набора 1, 3, 4 это выглядит так. Чтобы набрать N, можно:
- взять монету 1 — и тогда нам ещё нужно оптимально набрать N − 1;
- взять монету 3 — и оптимально набрать N − 3;
- взять монету 4 — и оптимально набрать N − 4.
Из этих вариантов выбираем тот, где монет в итоге меньше, и прибавляем одну — ту, что мы только что положили. Формула получается короткая: min(N) = 1 + наименьшее из min(N − 1), min(N − 3), min(N − 4). А самый маленький случай очевиден: min(0) = 0, ноль рублей набирается нулём монет.
Где прячется лишняя работа
Если запустить эту формулу как обычную рекурсию — функция вызывает сама себя для меньших сумм — она работает, но делает кучу лишнего. Чтобы посчитать min(6), ей нужны min(5), min(3) и min(2). Чтобы посчитать min(5) — снова min(2). И min(2) считается заново каждый раз, как будто мы про него уже не выясняли.
Это как готовить по рецепту, где на каждом шаге написано «а теперь снова с нуля сделай тесто», хотя ты уже замесил миску пять минут назад. Чем больше сумма, тем чудовищнее разрастается это дерево повторов — для больших чисел наивная рекурсия буквально зависает, пересчитывая одно и то же миллионы раз.
Запоминаем ответы: мемоизация
Лекарство до смешного простое: посчитал min(2) — запиши результат и в следующий раз просто загляни в записи вместо повторного счёта. Этот приём называют мемоизацией (да, без буквы «р» — от слова «memo», заметка). Заводим блокнотик-табличку: ключ — сумма, значение — минимум монет. Перед вычислением заглядываем в табличку; если ответ уже там, мгновенно его возвращаем.
Это и есть динамическое программирование сверху вниз: мы по-прежнему идём от большой задачи к маленьким, но не решаем одну и ту же подзадачу дважды. Каждое значение min(N) считается ровно один раз, и тяжёлое дерево повторов схлопывается в аккуратный список.
Строим таблицу снизу вверх
Есть и второй взгляд — снизу вверх. Вместо того чтобы спускаться от большой суммы, давай начнём с самой маленькой и пойдём вверх. Создаём массив, где ячейка с номером N хранит min(N). Заполняем по порядку: 0, 1, 2, 3 и так до нужной суммы. Когда дойдём до N, все меньшие значения уже посчитаны и лежат в массиве — бери и пользуйся.
Для монет 1, 3, 4 табличка растёт так:
- min(0) = 0 — стартовая точка;
- min(1) = 1 (одна монета 1);
- min(2) = 2 (1 + 1);
- min(3) = 1 (одна монета 3);
- min(4) = 1 (одна монета 4);
- min(5) = 2 (4 + 1);
- min(6) = 2 (3 + 3) — и вот он, правильный ответ, который проворонил жадный кассир.
Заметь красоту: чтобы посчитать любую ячейку, мы заглядываем всего лишь на пару клеток назад — на N − 1, N − 3, N − 4 — и берём готовое. Никакой рекурсии, никаких повторов, просто заполняем таблицу слева направо. Это похоже на то, как ты строишь башню из кубиков: верхний ряд держится на нижних, а нижние ты уже выложил и можешь на них опереться.
Зачем это всё на самом деле
Размен монет — это лишь удобная витрина. За той же идеей — «разбей задачу на пересекающиеся подзадачи и запоминай их ответы» — стоят вещи, которыми ты пользуешься каждый день. Навигатор ищет кратчайший путь, складывая его из кратчайших путей между промежуточными точками. Редактор показывает «возможно, вы имели в виду…», считая минимальное число правок до знакомого слова. Программы выравнивают цепочки ДНК по той же логике таблиц.
Так что в следующий раз, отсчитывая мелочь на кассе, вспомни: ты решаешь ту же задачу, над которой алгоритмы трудятся миллиарды раз в день. Только им нельзя ошибаться по-жадному — и поэтому они аккуратно заполняют свою маленькую табличку, клетку за клеткой, снизу вверх.