Постановка задачи.
Вам даны монеты разного номинала и общая сумма денег. Напишите функцию для вычисления количества комбинаций, составляющих эту сумму. Вы можете предположить, что у вас есть бесконечное количество монет каждого вида.
Пример 1:
Ввод: сумма = 5, монеты = [1, 2, 5]
Вывод: 4
Объяснение: существует четыре способа составить сумму:
5=5
5 =2+2+1
5=2+1+1+1
5=1+1+1+1+1
Пример 2:
Ввод: сумма = 3, монеты = [2]
Вывод: 0
Объяснение: сумма 3 не может быть составлена только из монет номиналом 2.
Пример 3:
Ввод: количество = 10, монет = [10]
Вывод: 1
Как решить проблему?
Чтобы подойти к решению, перечислите то, что мы знаем:
- У нас бесконечный запас каждой монеты[дано]
- Мы не можем сделать сумму меньше номинала монеты. [Мы не можем получить сумму 3, используя только монету номиналом 5]
- Самое главное, мы можем использовать предыдущую сумму для расчета следующей суммы. Проблема может быть разделена на более мелкие проблемы. [Чтобы получить сумму 5, мы можем приблизиться к этому, как мы можем сделать сумму 1, используя эти монеты и так далее]
Решение:
Ввод: количество = 5, монеты = [1, 2, 5]
Подход к решению:
Шаг 1: Рассмотрим список dp
sum_amount= [0, 0, 0, 0, 0, 0] ===> 6 элементов, потому что index — это сумма, которую мы стремимся получить здесь
Шаг 2: Инициализируйте список dp
sum_amount = [1, 0, 0, 0, 0, 0] ===> Мы можем сделать sum_amount[0] = 1 способом.
Шаг 3: Для каждой монеты выполните итерацию по массиву dp и попытайтесь составить сумму:
монеты = [1, 2, 5]
Для монеты 1 подумайте, как мы можем сделать индексную сумму нашего списка sum_amount, начиная с 1..5
Для монеты 1, количество 1 ==> мы можем сделать эту сумму способами current_value + sum_amount[1–1] =› sum_amount[0] способами =› [1, 1, 0, 0, 0, 0]
В основном, идея в том, если я рассматриваю эту монету, сколькими способами я могу компенсировать оставшуюся часть суммы . И именно поэтому инициализация dp[0] = 1 имеет смысл. Учитывая монету 1 для суммы 1, мне нужно сделать только сумму 0, и это можно сделать одним способом (поскольку я уже рассмотрел монету).
После завершения итерации монеты 1 sum_amount = [1, 1, 1 , 1, 1, 1] ==> Просто подразумевает, что сумма 1..5 может быть получена из монеты 1 только 1 способом.
Для монеты 2 сумма 1 => не может быть получена, пропустите эту сумму
Для монеты 2 сумма 2 => может быть получена одним способом, используя монету 2 + существующие способы, т. е. dp[2] = dp[2] + dp[2–2]
После полной итерации =› [1, 1, 2, 2, 3, 3]
Для монеты 5 пропускаются суммы с 1 по 4
Для монеты 5 сумма 5 =› dp[5] = dp[5] + dp[5–5] = 4
После завершения итерации =› dp = [1, 1, 2, 2, 3, 4]
Решение: дп[5]
Код:
Анализ сложности:
Пространственная сложность: O(количество), так как мы используем dp длины суммы
Временная сложность: O(количество*len(монеты)) ~ O(n²), мы повторяем dp для каждой монеты.
Чао.
