[LeetCode] 0322. Coin Change

Explore diverse LeetCode solutions in Python, C++, JavaScript, SQL, and TypeScript. Ideal for interview prep, learning, and code practice in multiple programming languages. Github Repo Link

Table of contents

Medium

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

Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

You may assume that you have an infinite number of each kind of coin.

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³¹ - 1
0 <= amount <= 10⁴

Python

				
					from functools import lru_cache
from typing import List


class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        @lru_cache(None)
        def dfs(amount):
            if amount < 0:
                return -1
            if amount == 0:
                return 0
            min_cost = float('inf')
            for coin in coins:
                res = dfs(amount - coin)
                if res != -1:
                    min_cost = min(min_cost, res+1)
            return -1 if min_cost == float('inf') else min_cost

        return dfs(amount)

Medium

Python

related articles