[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

内容目录

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

相关文章