Размен МонетCoin Change

Пусть dp[a] — минимальное число монет, необходимое для набора суммы a. Для каждой монеты номиналом c ≤ a, если сумма a-c уже набрана dp[a-c] монетами, то сумму a можно набрать, добавив ещё одну монету c: dp[a] = dp[a-c] + 1. Поскольку доступна не одна монета, а несколько номиналов, берём минимум по всем подходящим c: dp[a] = min по всем c ≤ a от (dp[a-c] + 1). Базовый случай dp[0] = 0 (нулевую сумму набирает пустой набор монет, без единой монеты). Если для какого-то a ни одна монета не подходит (или все пути через доступные c ведут к недостижимым a-c), dp[a] остаётся "недостижимо" — это сигнализирует, что сумму a вообще нельзя набрать данными номиналами.Let dp[a] be the minimum number of coins needed to make amount a. For each coin of denomination c ≤ a, if amount a-c can already be made with dp[a-c] coins, then amount a can be made by adding one more coin c: dp[a] = dp[a-c] + 1. Since more than one denomination is available, take the minimum over all eligible c: dp[a] = min over all c ≤ a of (dp[a-c] + 1). The base case is dp[0] = 0 (zero amount is made by an empty set of coins, no coin needed). If no coin works for some a (or every path through the available c leads to an unreachable a-c), dp[a] stays "unreachable" — signaling that amount a simply can't be made with these denominations.

Ключевое отличие от 0/1 рюкзака — в порядке обхода одномерного массива dp. И там, и там таблица одномерна по "ресурсу" (вместимость или сумма), но в рюкзаке при обходе по возрастанию a значение dp[a-c], которое уже пересчитано на текущей "волне" (с учётом текущего предмета), означало бы повторное использование этого же предмета — ошибка. В размене монет это НЕ ошибка, а именно то, что нужно: обходя a по возрастанию от 1 до amount и для каждого a перебирая все монеты c, мы намеренно допускаем, что dp[a-c] уже мог учитывать ту же самую монету c — это и реализует "неограниченное количество" каждого номинала. Другими словами: 0/1 рюкзак со сжатием в 1D требует внешнего цикла по предметам и внутреннего по вместимости в порядке убывания; размен монет можно организовать с внешним циклом по суммам a и внутренним по монетам (или наоборот, по монетам снаружи и суммам по возрастанию внутри) — оба варианта корректны именно потому, что переиспользование одной монеты в пределах одного a разрешено.The key difference from 0/1 knapsack is in the 1D array's traversal order. Both tables are one-dimensional over "resource" (capacity or amount), but in knapsack, traversing a in increasing order would mean dp[a-c] might already reflect the current item having been used on this same "wave" — reusing that same item, which is a bug. In coin change this is NOT a bug — it's exactly what's needed: by traversing a in increasing order from 1 to amount and, for each a, scanning every coin c, we deliberately allow dp[a-c] to have already accounted for that same coin c — that's precisely what implements "unlimited quantity" of each denomination. In other words: 0/1 knapsack compressed to 1D needs an outer loop over items and an inner loop over capacity in decreasing order; coin change can be organized with an outer loop over amounts a and an inner loop over coins (or coins outside and increasing amounts inside) — both are correct precisely because reusing one coin within the same a is allowed.

Близкий, но отдельный вариант задачи — не минимизация числа монет, а подсчёт ЧИСЛА СПОСОБОВ набрать сумму (например, сколькими различными наборами монет можно набрать сумму 11 из монет {1,5,10}). Рекуррентность там похожа, но с суммой вместо минимума: ways[a] += ways[a-c], и порядок вложенности циклов (монеты снаружи, суммы внутри) становится обязательным, а не одним из двух равнозначных вариантов — иначе один и тот же набор монет будет посчитан несколько раз в разном порядке как разные способы, что для счёта КОМБИНАЦИЙ (не важен порядок) неверно.A closely related but distinct variant of the problem isn't minimizing the coin count but counting the NUMBER OF WAYS to make the amount (e.g., how many distinct coin combinations make 11 out of {1,5,10}). The recurrence there looks similar but uses a sum instead of a minimum: ways[a] += ways[a-c], and the loop nesting order (coins outside, amounts inside) becomes mandatory rather than one of two equally valid choices — otherwise the same set of coins would get counted multiple times in different orders as distinct "ways," which is wrong for counting combinations (where order doesn't matter).

int coinChange(std::vector<int>& coins, int amount) {
    const int INF = 1e9;
    std::vector<int> dp(amount + 1, INF);
    dp[0] = 0;
    for (int a = 1; a <= amount; a++)             // по возрастанию — не по убыванию!// increasing — not decreasing!
        for (int c : coins)
            if (c <= a && dp[a - c] + 1 < dp[a])
                dp[a] = dp[a - c] + 1;
    return dp[amount] >= INF ? -1 : dp[amount];
}

Небольшой набор номиналов и целевая сумма — демонстрация проигрывает заполнение 1D-массива dp слева направо, для каждой суммы подсвечивая, какая монета и какая предыдущая ячейка дали минимум.A small set of denominations and a target amount — the demo auto-plays filling the 1D dp array left to right, highlighting for each amount which coin and which earlier cell produced the minimum.