Задача: Монетообменик

Сложность: Средняя

Условие задачи: дается массив, состоящий измонет определенного номинала, а также целевое значение суммы. 

Необходимо высчитать наименьшее количество монет, которыми можно получить необходимую сумму или вернуть -1 в случае невозможности. 

Количество монет не ограничено.

Пример:

Ввод: coins = [1,2,5], amount = 11

Вывод: 3

Объяснение: 11 = 5 + 5 + 1

Ввод: coins = [2], amount = 3

Вывод: -1

Ввод: coins = [1], amount = 0

Вывод: 0

Решение:

Код:

"""
Recursion + dp Caching
"""
import sys
class Solution(object):
    def coinChange(self, coins, amount):
        """
        :type coins: List[int]
        :type amount: int
        :rtype: int
        """
        def dp_solver(index, target, dp):
            if index == 0:
                if target % coins[0] == 0:
                    return  target / coins[0]

                return 1e9
            
            if dp.get((index,target)):
                return dp.get((index,target))
            

            not_take = 0 + dp_solver(index -1, target, dp)
            take = sys.maxint

            if coins[index] <= target:
                take = 1 + dp_solver(index, target - coins[index], dp)
            
            dp[(index, target)] = min(take, not_take)
            return dp[(index, target)]
        
        ans =  dp_solver(len(coins)-1, amount, {})
        if ans >= 1e9:
            return -1
        return ans