#106 Medium Time O(n·m) Space O(n) Animated

Coin Change

Find minimum number of coins to make up the amount.

LeetCode ↗

Tutor Mode Build the mental model before you memorize the code.

1 Predict
2 Trace
3 Explain
4 Implement

Pattern Dynamic programming: reuse smaller answers

Define one state whose value fully solves a smaller version of the problem.

Approach: Dynamic Programming (1D)

Click play to start

Step 0 / 0

Press play to start the visualization.

1×

Core Insight

Define one state whose value fully solves a smaller version of the problem.

Common Pitfall

Write the recurrence in words before optimizing the storage.

Description

Find minimum number of coins to make up the amount.

Constraints

Time Complexity: O(n·m)
Space Complexity: O(n)

Solution — Dynamic Programming (1D)

TimeO(n·m) SpaceO(n)

Implementation Plan

Translate the invariant into these small, testable moves.

Define the state precisely.
Set base cases.
Fill states in dependency order.
Return the final state.

def coinChange(coins, amount):
    dp = [amount + 1] * (amount + 1)
    dp[0] = 0
    
    for a in range(1, amount + 1):
        for c in coins:
            if a - c >= 0:
                dp[a] = min(dp[a], 1 + dp[a - c])
                
    return dp[amount] if dp[amount] != amount + 1 else -1

Decode Ways

Maximum Product Subarray

Coin Change

Steps

Description

Constraints

Tags

Solution — Dynamic Programming (1D)