Почему это работает
- Какими бы монетами ни платили a, одна из них идёт последней. Если это c, остальные платят a − c, в лучшем случае за dp[a − c] монет. Значит, dp[a] — наименьшее dp[a − c] + 1 по всем монетам.
- ∞ не даёт суммам, которые не оплатить, попасть в минимум: ∞ + 1 — всё ещё ∞. Поэтому монета 6 на 10 ничего не даёт — остаток 4 равен ∞, — и самая крупная монета не всегда правильная.
- Суммы идут вверх от 1, а a − c всегда меньше a, так что всё, что читает клетка, уже посчитано окончательно.
Сложность
Время O(сумма × монеты): каждая сумма один раз пробует каждую монету. Память O(сумма): по клетке на каждую сумму от 0.
дальшеТеперь реши её сам, без подсказок.
Решить на LeetCode ↗