322. Coin Change

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money

Example 1:

• Input: coins = [1,2,5], amount = 11
• Output: 3
• Explanation: 11 = 5 + 5 + 1

Example 2:

• Input: coins = [2], amount = 3
• Output: -1

Example 3:

• Input: coins = [1], amount = 0
• Output: 0

Constraints:

• 1 <= coins.length <= 12
• 1 <= coins[i] <= 2^31 - 1
• 0 <= amount <= 10^4

Solution

from math import inf


class Solution:
    def coinChange(self, coins: list[int], amount: int) -> int:
        n = len(coins)
        memo = [[-1] * (amount + 1) for _ in range(n + 1)]

        def min_coins(coins, i, amount, memo):
            if amount == 0:
                return 0
            if i == 0 or amount < 0:
                return inf
            if memo[i][amount] != -1:
                return memo[i][amount]

            skip = min_coins(coins, i - 1, amount, memo)
            use = min_coins(coins, i, amount - coins[i - 1], memo)
            if use != inf:
                use += 1

            memo[i][amount] = min(skip, use)
            return memo[i][amount]

        result = min_coins(coins, n, amount, memo)
        return result if result != inf else -1  # pyright: ignore[reportReturnType]