322. Coin Change
Category: /leetcodeYou are given coins of different denominations and a total amount of money amount. Write a function to compute 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.
top-down
def coinChange(self, coins: List[int], amount: int) -> int:
memo = {}
def dp(n):
""" get N from subproblems """
# check result
if n in memo: return memo[n]
# base
if n == 0: return 0
if n < 0: return -1
# solve sub problems
res = float("inf")
for coin in coins:
sub_res = dp(n - coin)
if sub_res == -1: continue
res = min(res, sub_res + 1)
# save result to memo
memo[n] = res if res != float("inf") else -1
return memo[n]
return dp(amount)
bottom-up
def coinChange(self, coins: List[int], amount: int) -> int:
# plus base, make array as `size + 1`
dp = [float("inf")] * (amount + 1)
# base case
dp[0] = 0
# iterate all states
for i in range(len(dp)):
# go over each choice
for coin in coins:
# skip invalid sub problem
if (i - coin) < 0: continue
# check optimal sub-problem
dp[i] = min(dp[i], dp[i - coin] + 1)
return dp[amount] if dp[amount] != float("inf") else -1
