#322
Coin Change
medium· 1-D DPruns: 0You are given an integer array coins representing coin denominations and an integer amount representing a total. Return the fewest number of coins needed to make up that amount. If it cannot be made up, return -1. You may assume you have an infinite supply of each coin.
sign in to paste and practice your own solution
wpm 0acc 100%time 0:000 / 362
class Solution:
def coinChange(self, coins: list[int], amount: int) -> int:
dp = [amount + 1] * (amount + 1)
dp[0] = 0
for a in range(1, amount + 1):
for coin in coins:
if a - coin >= 0:
dp[a] = min(dp[a], dp[a - coin] + 1)
return dp[amount] if dp[amount] != amount + 1 else -1
click the box to focus · tab inserts 4 spaces · backspace to correct · esc to pause
desktop only
codedrill is a typing game and needs a real keyboard. open this on a laptop or desktop to practice.
you can still browse problems and sections from your phone.