https://leetcode.com/problems/coin-change

This is classical dynamic programming problem. Let us define state dp(i) as the answer to the question: what is the minimum number of coins we need to get value i. Then:

  1. If i == 0, then we need no coins at all, so we return 0.
  2. if i < 0, so we are trying to make negative sum, which is not posible, so we return minus infinity as indicator that it is not possible.
  3. In other case, we check all dp(i - coin) for every coin and add 1 to the result.

Complexity: time complexity is O(amount * n), where n is number of coins, because: we have O(amount) different states and we have n choices to go from any state. Space complexity is the same.

class Solution:
    def coinChange(self, coins, amount):
        @lru_cache(None)
        def dp(i):
            if i == 0: return 0
            if i < 0: return float("inf")
            return min(dp(i - coin) + 1 for coin in coins)
        
        return dp(amount) if dp(amount) != float("inf") else -1

If you like the solution, you can upvote it on leetcode discussion section: Problem 0322