Сдача минимальным числом монет
Набрать сумму минимальным числом монет — жадность часто врёт, динамика честна.
1function coinChange(coins: number[], amount: number): number {2 const INF = Infinity3 const dp = [0] // dp[s] = минимальное монет для суммы s4 for (let s = 1; s <= amount; s++) dp[s] = INF5 6 for (let s = 1; s <= amount; s++) {7 for (const c of coins) {8 if (c <= s && dp[s - c] + 1 < dp[s]) {9 dp[s] = dp[s - c] + 110 }11 }12 }13 14 return dp[amount] === INF ? -1 : dp[amount]15}Проблема
Набрать сумму минимальным числом монет — жадность часто врёт, динамика честна.
Что вы видите
Ряд сумм: dp[s] — минимум монет; каждая монета пробует улучшить меньшую сумму.
Как это работает
dp[s] = min(dp[s−c] + 1) по монетам c. Жадный «крупными сначала» ломается на монетах {1,3,4} и сумме 6: даст 4+1+1 вместо 3+3 — классический контрпример в пользу динамики.
Пошаговый разбор
- 01
Сумма
Перебираем от 1 до amount.
- 02
Монета
dp[s−c]+1 против dp[s].
- 03
Ответ
dp[amount] или −1.
Complexity и ограничения
Сложность см. в шапке страницы.
Edge cases
- Пустой вход
Корректная тривиальная обработка.
- Вырожденный случай
Минимум работы — сразу ответ.
Где встречается в реальности
Платёжные системы
Размен и округление сумм в кассах.
Тайминги
Минимальное число интервалов на задачу.
Учебник
Жадность vs DP — контрпример №1.
Связанные алгоритмы
«Почему кассир с жадностью иногда ошибается»
Тот же сценарий StepSequence в вертикальной композиции — с safe zones и записью WebM ниже на странице.
Shorts 9:16
Вертикальная композиция строится той же последовательностью шагов, что и страница: safe zones отмечены пунктиром (там живёт UI платформ), биты сценария подсвечиваются по прогрессу. Кнопка записи сохраняет WebM — детерминированная StepSequence даёт воспроизводимый ролик без монтажа.