Объясни задачу о размене монет
Вопрос
Объясни решение задачи «минимальное число монет для суммы» и его сложность. Почему тут не подходит жадность?
Попробуйте сами
Ответьте вслух за 2 минуты, как на собесе. Потом сверьтесь с тезисами: что прозвучало, а что нет.
Показать ответ и разбор
Коротко
Что должно прозвучать в ответе
Показывает контрпример для жадности
Формулирует состояние: dp[s] минимум монет для суммы s
Переход: dp[s] = min(dp[s - c] + 1) по монетам
База dp[0] = 0, остальные Infinity, недостижимо → -1
O(S · k) времени, O(S) памяти
Что могут спросить следом
- Как посчитать число способов вместо минимума?
- Как восстановить сами монеты?
- Как решить сверху вниз?
Разбор
Жадность ломается: при монетах 1, 3, 4 и сумме 6 она даст 4 + 1 + 1, а оптимум 3 + 3. Поэтому динамика. Состояние: dp[s] это минимальное число монет, чтобы набрать сумму s. Переход: последняя монета какая-то c, значит dp[s] = min по всем c ≤ s от dp[s - c] + 1. База: dp[0] = 0, всё остальное Infinity, то есть пока недостижимо. Считаю s от 1 до S, ответ dp[S] или -1, если остался Infinity. Время O(S · k), где k число номиналов, память O(S). Чтобы восстановить монеты, храню для каждой суммы, какой монетой пришли. Для числа способов меняю min на сумму и внешний цикл делаю по монетам, чтобы не считать перестановки.
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.