GitHub
Задачи с собеседований: размен
Проблема размена часто встречается в интервью Facebook и Amazon. Вам даются номиналы монет и желаемую сумму денег. Исходя из этого, вам нужно написать функцию для вычисления наименьшего количества монет, которое вам нужно, чтобы собрать эту сумму. Если вы не можете получить указанную сумму денег ни с одной комбинацией монет, вы возвращаете -1.
Вот три способа решить эту проблему:
- Перебор (брутфорс)
- Нисходящее динамическое программирование с мемоизацией
- Восходящее динамическое программирование с табуляризацией
Давайте посмотрим на решение, использующее восходящее динамическое программирование с табуляризацией на C++:
Для каждой итерации внутреннего цикла мы получаем решение с denoms[j] и сохраняем его в x. Мы также получаем решение без denoms[j] и сохраняем его в y. Таким образом мы можем ссылаться на более ранние решения, чтобы избежать дублирования вычислений.
Для каждой монеты номинала может быть только две возможности: включить ее или исключить. Мы знаем, что если монета denom[j] больше, чем amount, то x устанавливается в 0, так как включение ее в рассмотрение невозможно.
Временная сложность равна *O (amount * denomsLength), что является количеством итераций цикла for.
Примечание. Каждый из этих трех методов оценивается через временную сложность, а это означает, что временная сложность является важным понятием, которое необходимо понимать, чтобы добиться успеха в проблеме обмена монет.
