Динамическое программирование: состояние, переход и порядок

Есть монеты номиналов 1,3,4. Сумму 6 можно набрать как 4+1+1 или 3+3. Правило «брать самую большую подходящую» использует три монеты, хотя достаточно двух. Нужно сравнить варианты, но не пересчитывать одинаковые оставшиеся суммы снова и снова.

Определяем подзадачу

Пусть dp[a] — минимальное число монет для суммы a при неограниченном числе монет каждого заданного номинала. dp[0]=0: пустой набор составляет нулевую сумму. Если сумму составить нельзя, храним отдельное недостижимое значение. Условия задачи важны: при одной монете каждого вида состояние и порядок вычисления будут другими.

Для a>0 рассмотрим последнюю монету c. До неё нужно оптимально составить a−c. Тогда кандидат равен dp[a−c]+1. Минимум всех допустимых кандидатов даёт dp[a]. Мы не угадываем магическую формулу: перебираем последнее действие, которое могло привести к ответу.

dp := make([]int, amount+1)
for a := 1; a <= amount; a++ {
    dp[a] = amount + 1
    for _, c := range coins {
        if c <= a && dp[a-c]+1 < dp[a] {
            dp[a] = dp[a-c]+1
        }
    }
}

Номиналы должны быть положительными. Нулевая монета не уменьшает подзадачу, отрицательная обращается в будущее и может разрушить смысл стоимости. Эталон валидирует вход, ограничивает учебную amount до миллиона, а итоговое значение выше amount преобразует в ответ−1. Это предел модели ресурсов, не математический предел задачи.

Почему состояния достаточно

Лучший способ набрать a заканчивается некоторой монетой c. Если предыдущая часть не минимальна для a−c, можно заменить её лучшей и уменьшить весь набор. Значит оптимальный ответ состоит из оптимальной подзадачи и одного последнего действия. Такое свойство называют оптимальной подструктурой.

Повторяющиеся подзадачи — другая часть метода. Например, сумма 2 нужна при построении 3 с монетой 1 и 5 с монетой 3. Сохранённый dp[2] избавляет от повторного перебора. Одной оптимальной подструктуры ещё недостаточно, чтобы любое решение нуждалось в большой таблице.

В каком порядке считать

Положительный c означает a−c<a. Поэтому возрастающий порядок a вычисляет нужные результаты до обращения к ним. Это явный граф зависимостей подзадач. Memoization вычисляла бы состояния рекурсивно по требованию и сохраняла ответы; bottom-up заполняет таблицу в выбранном порядке. Обе версии нуждаются в корректном состоянии и базе.

На [1,3,4]: dp[0..6]=0,1,2,1,1,2,2. При 6 последний c=3 обращается к dp[3]=1 и даёт 2. Сложность O(A·K), где A — сумма, K — число номиналов; память O(A). По числу бит записи A это псевдополиномиальная оценка: увеличение числа с миллиона до миллиарда требует гораздо больше ячеек, хотя строка ввода удлинилась ненамного.

Восстанавливаем конкретное решение

Чтобы вернуть номиналы, сохраняйте выбранную последнюю монету для каждого улучшения. Затем двигайтесь от amount к amount−chosen[amount], пока не придёте к 0. Для недостижимого состояния не начинайте восстановление. При нескольких оптимальных наборах договор может разрешать любой либо устанавливать правило равенства отдельно.

Нельзя восстанавливать набор просто по последней просмотренной монете: она могла не улучшить dp. Parent хранит принятое решение, а не историю всех попыток.

Самостоятельная практика

Заполните MinCoins в exercises и выполните go test ./exercises -run TestMinCoins. Допишите невозможную сумму, amount=0, пустой набор и невалидные номиналы. Затем добавьте восстановление списка и проверьте его сумму, количество и принадлежность номиналов входу.

Независимый эталон для маленьких сумм можно построить как BFS по суммам 0..A, где добавление одной монеты — одно ребро. Практика — 60 минут.

Критерии готовности: смысл состояния записан до кода; база и недостижимость различаются; переход использует уже вычисленное состояние; ответ и его восстановление согласованы; цена зависит от A, а не только числа монет.

Разбор

Для coins=[2],amount=3 ответ−1; для пустого coins иamount=0 —0. Контрпример 6 на 1,3,4 показывает, почему жадный выбор требует доказательства. В следующей главе найдём задачу, где такой выбор действительно обоснован.

Источники: MIT 6.006: лекции по dynamic programming, Princeton: shortest paths и связи с оптимизацией.