202401232108
tags: #dp

class Solution(object):
	def coinChange(self, coins, amount):
		memo = {}
		memo[0] = 0
		for coin in coins:
			memo[coin] = 1
		def dp(amount):
			if amount < 0:
				return float('inf')
			if amount in memo:
				return memo[amount]
			res = float('inf')
			for coin in coins:
				res = min(res, 1 + dp(amount - coin))
			memo[amount] = res
			return res
		res = dp(amount)
		return res if res != float('inf') else -1

Reference

https://leetcode.com/problems/coin-change/