Coin Change
コイン額面の配列 coins と整数 amount が与えられる。amount を作るために必要な最小枚数を返す。作れない場合は -1 を返す。コインは無限に使える。
Example 1:
Input: coins = [1,5,10], amount = 11
Output: 2
Example 2:
Input: coins = [2], amount = 3
Output: -1
Constraints:
使用した概念Dynamic Programming
アプローチ
思考
- メモ化再帰（トップダウン DP）
dp(n)= 残額nを作る最小枚数- 各コインで
dp(n - coin)を試して最小を取る
実装
from functools import lru_cache
class Solution:
def coinChange(self, coins: list[int], amount: int) -> int:
@lru_cache(maxsize=None)
def dp(n: int) -> int:
if n == 0:
return 0
if n < 0:
return float('inf') # type: ignore
return min(dp(n - c) + 1 for c in coins)
result = dp(amount)
return result if result != float('inf') else -1Time Space