You are given an integer array coins representing coins of various denominations and an integer amount. Return the fewest number of coins needed to make up that amount. If it cannot be made, return -1. Bottom-up DP: Build a table where dp[x] = minimum coins to reach amount x. For each coin, update all reachable amounts.

The step-through player is coming for this one. Two Sum has the full animation today; the rest are being authored in the admin.

Pythontime O(amount × coins) · space O(amount)

def coinChange(coins: list[int], amount: int) -> int:
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    for coin in coins:
        for x in range(coin, amount + 1):
            dp[x] = min(dp[x], dp[x - coin] + 1)
    return dp[amount] if dp[amount] != float('inf') else -1

Next upNumber of Islands

Two Sum is free. Enroll to unlock every visualization and save where you stopped.Enroll free

Watch the video walkthrough