Постановка проблемы
Предположим, у нас есть монеты достоинством [1, 2, 5], а общая сумма равна 7. Мы можем внести изменения следующими 6 способами:
Подсказка
- Используйте принципы динамического программирования
Попробуйте сами
- путь> C ++
- путь> C ++
- путь> C ++
- Java
- Java
- Python
- Python
- JavaScript
- JavaScript
- Рубин
- Рубин
int resolve_coin_change (vector & denominations, int amount) {//TODO: Write - Your - Code return -1;}
Решение
- C ++
- C ++
- C ++
- Java
- путь> Java
- Python
- Python
- JavaScript
- JavaScript
- Ruby
- Ruby
int resolve_coin_change (vector & denominations, int amount) {vector решение (количество + 1); решение [0] = 1; for (int den: деноминации) {for (int i = den; i denominations = {1, 2, 5}; int amount = 7; int result = resolve_coin_change (номиналы, сумма); //вывод результата cout
Объяснение решения
Сложность выполнения
Сложность выполнения этого решения квадратичная, O (m × n), где m — количество номиналов, а n — общая сумма.
Сложность памяти
Сложность памяти этого решения линейна, O (n), где n — общий объем.
Анализ решения
Для применения подхода динамического программирования решаемая проблема должна иметь оптимальную подструктуру. Оптимальная структура означает, что оптимальное решение рассматриваемой проблемы может быть достигнуто за счет использования оптимальных решений ее подзадач и перекрывающихся подзадач. Один из способов добиться этого — использовать предварительно вычисленные значения для решенных подзадач, чтобы нам не приходилось решать их снова.
Проблема смены монеты имеет оптимальную подструктуру, что означает, что она можно легко разделить на более простые задачи, и их можно решить, чтобы найти окончательное решение. Он также удовлетворяет свойству перекрытия подзадач, то есть результаты ранее решенных подзадач можно использовать несколько раз.
Для решения этой проблемы мы сохраним массив размером amount +1 . Одно дополнительное место зарезервировано, потому что мы также хотим сохранить решение для суммы 0 .
Есть только один способ изменить 0 , т. е. выберите без монеты, поэтому мы инициализируем solution [0] = 1 . Мы решим проблему для каждой суммы, от номинала к сумме, используя монеты до номинала, den .
Результаты разных номиналов должны храниться в решение массива.
Решение для суммы x с использованием номинала den будет тогда:
решение [x] = решение [x] + решение [x - den]
Мы повторим этот процесс для всех номиналов и последний элемент массива solution , у нас будет решение.
Учитывая пример, упомянутый выше, код работает следующим образом:
-
Первоначально
solution [0] = 1иsolution [x] = 0для всехx> 0иx . -
Мы начнем с первого номинала, который в нашем примере равен
1, и обновим решение. [x] = решение [x] + решение [x - 1]для всех1 . -
Теперь в нашем примере мы будем использовать второй номинал, то есть
2. Мы вычислимрешение [x] = решение [x] + решение [x - 2]для всех2 . -
В конце, в нашем примере мы будем использовать третий номинал, то есть
5. Мы вычислимрешение [x] = решение [x] + решение [x - 5]для всех5 .
