Coin Change

Средняя№322одномерный массив

Даны номиналы монет, каждой сколько угодно, и сумма. Нужно набрать ровно эту сумму как можно меньшим числом монет или вернуть -1, если это невозможно. Наш пример: монеты [3, 5, 6], сумма 10 — 2 монеты, 5 + 5.

322 Coin ChangeРазбор · 1×

Пример: монеты [3, 5, 6], сумма 10. Смотрите на сумму 10: самая крупная монета 6 никуда не ведёт.

монеты356dp0∞1∞2∞3∞4∞5∞6∞7∞8∞9∞10∞
эта сумма, эта монетазаполнено, ∞ — не оплатитьберём отсюдаответ и его монеты

dp[a]: наименьшее число монет, чтобы заплатить ровно a. Сначала все суммы — ∞, пока не оплачиваются

01/44
сначала · назад · пуск · шаг
Скорость
1function coinChange(coins, amount):
2 dp = array of size amount + 1, all ∞
3 dp[0] = 0 // nothing to pay
4 for a from 1 to amount:
5 for each c in coins:
6 if c <= a:
7 dp[a] = min(dp[a], dp[a - c] + 1)
8 if dp[amount] == ∞:
9 return -1
10 return dp[amount]
состояние
dp
[∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞]
a
–
c
–
историянажмите шаг, чтобы вернуться

← → шаг · пробел — пауза

Почему это работает

  1. Какими бы монетами ни платили a, одна из них идёт последней. Если это c, остальные платят a − c, в лучшем случае за dp[a − c] монет. Значит, dp[a] — наименьшее dp[a − c] + 1 по всем монетам.
  2. ∞ не даёт суммам, которые не оплатить, попасть в минимум: ∞ + 1 — всё ещё ∞. Поэтому монета 6 на 10 ничего не даёт — остаток 4 равен ∞, — и самая крупная монета не всегда правильная.
  3. Суммы идут вверх от 1, а a − c всегда меньше a, так что всё, что читает клетка, уже посчитано окончательно.

Сложность

Время O(сумма × монеты): каждая сумма один раз пробует каждую монету. Память O(сумма): по клетке на каждую сумму от 0.

дальшеТеперь реши её сам, без подсказок.

Решить на LeetCode ↗

Задача и её условие принадлежат LeetCode. Здесь — наш пересказ, наш пример и наше решение. Patterns Hero не связан с LeetCode.