Сложность: medium
Дан целочисленный массив coins, представляющий монеты разных номиналов, и целое число amount, представляющее общую сумму денег.
Верните минимальное количество монет, необходимых для составления этой суммы. Если эту сумму невозможно составить с помощью комбинации монет, верните -1.
Вы можете предположить, что у вас есть неограниченное количество монет каждого типа.
Пример:
Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1
👨💻 Алгоритм:
1⃣Инициализация и вызов функции backtracking
Инициализируйте переменные для хранения минимального количества монет и вызовите функцию backtracking с начальными параметрами.
2⃣Функция backtracking
Внутри функции backtracking для каждой монеты из массива coins:
Проверьте все возможные количества монет данного номинала (от 0 до максимального количества, которое можно использовать без превышения amount). Для каждой комбинации монет обновите сумму и вызовите функцию рекурсивно для проверки оставшейся суммы. Если текущая комбинация дает меньшую сумму монет, обновите минимальное количество монет.
3⃣Возврат результата
Если комбинация, дающая сумму amount, найдена, верните минимальное количество монет, иначе верните -1.
😎 Решение:
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
return self._coinChange(0, coins, amount)
def _coinChange(self, idxCoin: int, coins: List[int], amount: int) -> int:
if amount == 0:
return 0
if idxCoin < len(coins) and amount > 0:
maxVal = amount // coins[idxCoin]
minCost = float('inf')
for x in range(maxVal + 1):
if amount >= x * coins[idxCoin]:
res = self._coinChange(idxCoin + 1, coins, amount - x * coins[idxCoin])
if res != -1:
minCost = min(minCost, res + x)
return -1 if minCost == float('inf') else minCost
return -1
Ставь 👍 и забирай 📚 Базу знаний