LeetCode 322 Coin Change - Implementation

Bottom-up DP. Try each coin for each amount.

def coinChange(coins, amount): dp = [float('inf')] * (amount + 1) dp[0] = 0

for i in range(1, amount + 1):
    for coin in coins:
        if coin <= i and dp[i - coin] != float('inf'):
            dp[i] = min(dp[i], dp[i - coin] + 1)

return dp[amount] if dp[amount] != float('inf') else -1

$O(\text{amount} \times n)$ time, $O(\text{amount})$ space.