[LeetCode] 0322.コインチェンジ

Python、C++、JavaScript、SQL、TypeScript の多様な LeetCode ソリューションを探索してください。面接の準備、学習、複数のプログラミング言語でのコードの練習に最適です。 Github リポジトリリンク

中くらい

整数配列が与えられます コイン さまざまな額面のコインと整数を表す 額 合計金額を表します。

戻る その金額を補うために必要なコインの最小数コインのどの組み合わせでもその金額を補えない場合は、返却してください。 -1.

各種類のコインを無限に持っていると考えるかもしれません。

例 1:

入力： コイン = [1,2,5]、金額 = 11
出力： 3
説明： 11 = 5 + 5 + 1

例 2:

入力： コイン = [2]、金額 = 3
出力： -1

例 3:

入力： コイン = [1]、金額 = 0
出力： 0

制約:

1 <= コイン.長さ <= 12
1 <= コイン[i] <= 2 ³¹ - 1
0 <= 金額 <= 10 ⁴

パイソン

				
					functools から lru_cache を入力して import List クラス 解決策: def CoinChange(self, Coins: List[int], amount: int) -> int: @lru_cache(None) def dfs(amount): if amount < 0: return -1金額 == 0 の場合: 0 を返す min_cost = float('inf') (コイン単位のコインの場合): 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)

中くらい

パイソン

関連記事