6. Coin Change
«Экономия времени и ресурсов начинается с отказа от близоруких решений».
— Брайан Керниган
Задача о размене монет (Coin Change, LeetCode 322) — фундаментальный представитель семейства задач о неограниченном рюкзаке (Unbounded Knapsack).
Если в 4. House Robber каждый дом можно было ограбить лишь однажды (задача типа 0/1 Knapsack), то здесь любой номинал монеты доступен в бесконечном количестве экземпляров. Наша цель — набрать целевую сумму amount, используя минимальное суммарное число монет.
1. Постановка задачи и почему жадность терпит крах
Условие:
Дан массив целых чисел coins (номиналы доступных монет) и целевая сумма amount.
Верните минимальное число монет, необходимое для составления суммы. Если составить сумму невозможно ни при каких комбинациях, верните -1.
Вход: coins = [1, 3, 4], amount = 6
Выход: 2
Пояснение: оптимальный набор — 3 + 3 = 6 (2 монеты).
Ловушка «жадного» банкира
В реальной жизни (например, при расчете сдачи в рублях или долларах) мы всегда инстинктивно берем монету наибольшего номинала: чтобы выдать 48 рублей, берем $10 \times 4 + 5 + 2 + 1$. Жадный выбор работает в канонических валютных системах благодаря их особому математическому свойству (матроиды).
Но в произвольной системе номиналов жадность терпит сокрушительное фиаско:
- Монеты:
[1, 3, 4], сумма:6. - Жадный выбор: берем самую крупную монету $4$. Остаток $2$. Берем $1$ и еще $1$. Итог: $4 + 1 + 1$ = 3 монеты.
- Глобальный оптимум: $3 + 3$ = 2 монеты!
Жадный выбор ослеплен сиюминутной выгодой и заводит в тупик. Единственный способ найти оптимум — использовать динамическое программирование.
2. Формулировка 1D DP: Рекуррентное соотношение
Определим состояние:
Пусть $dp[i]$ — минимальное число монет, необходимое для набора точной суммы $i$.
Чтобы набрать сумму $i$, мы могли сделать последний шаг любой из доступных монет $c \in \text{coins}$ (при условии, что $c \le i$).
Перед добавлением этой монеты у нас была сумма $i - c$, для которой наилучший ответ уже найден в $dp[i - c]$.
Следовательно, мы перебираем все монеты и выбираем минимум:
$$dp[i] = \min_{c \in \text{coins}, \, c \le i} \Big(dp[i - c] + 1\Big)$$
Базовый случай и выбор «бесконечности»:
- $dp[0] = 0$ (для суммы 0 требуется 0 монет).
- Все остальные значения $dp[1 \dots \text{amount}]$ инициализируются условной «бесконечностью».
flowchart TD
classDef process fill:#1e293b,stroke:#38bdf8,stroke-width:1px,color:#f8fafc
classDef success fill:#064e3b,stroke:#34d399,stroke-width:1px,color:#f8fafc
classDef error fill:#7f1d1d,stroke:#f87171,stroke-width:1px,color:#f8fafc
classDef warning fill:#78350f,stroke:#fbbf24,stroke-width:1px,color:#f8fafc
classDef entry fill:#1e3a5f,stroke:#38bdf8,stroke-width:2px,color:#f8fafc
Start["Сумма i"]:::entry --> LoopCoins{"Перебор монеты c"}:::warning
LoopCoins -- "c > i" --> Skip["Не помещается<br/>(пропуск)"]:::process
LoopCoins -- "c <= i" --> Calc["Остаток i - c<br/>Берем dp[i - c]"]:::process
Calc --> Add["Стоимость: dp[i - c] + 1"]:::process
Add --> Upd["dp[i] = min(dp[i], dp[i - c] + 1)"]:::success
Upd --> Next{"Есть еще монеты?"}:::warning
Next -- "Да" --> LoopCoins
Next -- "Нет" --> Done["dp[i] вычислен"]:::entry
3. Реализация на Go 1.22+
В Go 1.21+ функция min() встроена в язык. В качестве безопасной бесконечности идеальным выбором является amount + 1: даже если бы мы собирали сумму одними копейками по 1, потребовалось бы максимум amount монет. Любое значение $\ge amount + 1$ физически недостижимо и гарантированно защищает от целочисленного переполнения при сложении.
package knapsack
// CoinChange возвращает минимальное число монет для набора суммы amount.
// Временная сложность: O(amount * len(coins)).
// Пространственная сложность: O(amount).
func CoinChange(coins []int, amount int) int {
if amount < 0 {
return -1
}
if amount == 0 {
return 0
}
// Страж бесконечности: amount + 1 заведомо больше любого валидного ответа.
// Использование amount + 1 защищает от integer overflow при + 1.
inf := amount + 1
dp := make([]int, amount+1)
// Инициализируем недостижимые суммы
for i := 1; i <= amount; i++ {
dp[i] = inf
}
dp[0] = 0
// Заполнение таблицы снизу вверх
for i := 1; i <= amount; i++ {
for _, c := range coins {
if c <= i {
dp[i] = min(dp[i], dp[i-c]+1)
}
}
}
if dp[amount] > amount {
return -1 // Сумму набрать невозможно
}
return dp[amount]
}
4. Восстановление пути: Какие именно монеты взять?
На реальном интервью вас неизбежно попросят:
«Алгоритм возвращает число 2. А какие именно монеты вошли в этот оптимум?»
Для реконструкции ответа заводим дополнительный массив предков parent:
func CoinChangeWithCoins(coins []int, amount int) (int, []int) {
inf := amount + 1
dp := make([]int, amount+1)
parentCoin := make([]int, amount+1)
for i := 1; i <= amount; i++ {
dp[i] = inf
parentCoin[i] = -1
}
for i := 1; i <= amount; i++ {
for _, c := range coins {
if c <= i && dp[i-c]+1 < dp[i] {
dp[i] = dp[i-c] + 1
parentCoin[i] = c // Запоминаем монету, давшую оптимум
}
}
}
if dp[amount] > amount {
return -1, nil
}
// Восстановление траектории
resultCoins := make([]int, 0, dp[amount])
curr := amount
for curr > 0 {
c := parentCoin[curr]
resultCoins = append(resultCoins, c)
curr -= c
}
return dp[amount], resultCoins
}
5. Mechanical Sympathy: Порядок циклов и L1/L2 Cache Locality
В нашем алгоритме внешний цикл идет по суммам i, а внутренний — по монетам c.
При вычислении dp[i] мы обращаемся к ячейкам dp[i - c].
Если номиналы монет сильно разнесены (например, coins = [1, 5000]), обращение к dp[i - 5000] вызывает нелокальный прыжок по памяти. Для огромных сумм (amount = 10^6, слайс занимает 8 МБ) прыжки назад будут постоянно вызывать промахи мимо L1/L2 кэша (Cache Misses).
flowchart LR
classDef process fill:#1e293b,stroke:#38bdf8,stroke-width:1px,color:#f8fafc
classDef success fill:#064e3b,stroke:#34d399,stroke-width:1px,color:#f8fafc
classDef warning fill:#78350f,stroke:#fbbf24,stroke-width:1px,color:#f8fafc
classDef entry fill:#1e3a5f,stroke:#38bdf8,stroke-width:2px,color:#f8fafc
subgraph Memory["Срез dp в виртуальной памяти"]
M1["dp[i-5000] (Далекая кэш-линия)"]:::warning
M2["..."]:::process
M3["dp[i-1] (Текущая кэш-линия)"]:::process
M4["dp[i]"]:::entry
end
M1 -. "Cache Miss (задержка ~50 нс)" .-> M4
M3 -. "Cache Hit (~1 нс)" .-> M4
Если поменять циклы местами (внешний по монетам, внутренний по суммам от c до amount), шаг обращения к памяти внутри цикла станет строго последовательным: $dp[i] = \min(dp[i], dp[i-c] + 1)$. Аппаратный префетчер процессора будет читать память с постоянным шагом, ускоряя выполнение на 20–40% на больших массивах данных.
6. Применение в System Design и бэкенде
- Memory Sizing в аллокаторах (Go runtime mcache/mcentral):
Рантайм Go не аллоцирует произвольные байты. Он оперирует классами размеров (Size Classes: 8, 16, 24, 32, 48, 64, 80... байт). Выбор оптимальной комбинации span-блоков памяти для покрытия запроса — это прямая вариация Coin Change. - Пакетная передача в сетях (MTU / TCP Chunks):
Разбиение полезной нагрузки на сегменты разного допустимого размера с минимизацией оверхеда заголовков IP/TCP.
Итог
- Неограниченный рюкзак: Монеты можно использовать повторно сколько угодно раз, поэтому мы итерируемся по всей таблице слева направо.
- Безопасная бесконечность: Используйте
amount + 1вместоmath.MaxInt, чтобы исключить арифметическое переполнение при+ 1. - Реконструкция ответа: Сохранение выбранного номинала в массиве
parentпозволяет восстановить полный путь за $O(K)$ шагов.
В следующей лекции мы разберем интервальную задачу о лестнице с затратами, объединяющую паттерны стоимости и линейного шага: 7. Min Cost Climbing Stairs.