ToolMight LogoToolMight
MediumDynamic ProgrammingPattern: Bottom-Up TabulationPattern: Unbounded Knapsack

Coin Change

Compute the fewest number of coins needed to make up a given amount. The quintessential problem for learning bottom-up dynamic programming tabulation and overlapping subproblems.

Problem Statement

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.

Return 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.

Examples & Constraints

Example 1
Input: coins = [1, 2, 5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1. Total 3 coins.
Example 2
Input: coins = [2], amount = 3
Output: -1
Explanation: Amount 3 cannot be formed using only coins of denomination 2.
Constraints
  • 1 <= coins.length <= 12
  • 1 <= coins[i] <= 2^31 - 1
  • 0 <= amount <= 10^4

Bottom-Up Dynamic Programming (Tabulation)

Optimal Approach
Time:O(S * n)
Space:O(S)

Build an array dp where dp[i] represents the minimum coins needed for amount i. For each amount, test all coins and pick the minimum of 1 + dp[i - coin] in O(amount * len(coins)) time.

Time ComplexityO(S * n)

Where S is the target amount and N is the number of coin denominations. The outer loop runs S times, and the inner loop checks N coins.

Space ComplexityO(S)

Consumes an array dp of size amount + 1 to store subproblem solutions.

Underlying algorithmic logic

Why Greedy Fails for Arbitrary Coins

Humans naturally try to pick the largest coin first (Greedy approach).
For example, with coins [1, 3, 4] and amount 6:

  • Greedy picks 4 then 1 then 1 = 3 coins (4 + 1 + 1).
  • But the optimal combination is 3 + 3 = 2 coins!

Because greedy choices do not guarantee the global optimum for arbitrary denominations, we must evaluate overlapping subproblems using Dynamic Programming.

The Recurrence Relation:

Let dp[a] be the minimum coins needed to make amount a.

  1. Base Case: dp[0] = 0 (zero coins needed to form amount 0).
  2. Initialize all other entries dp[1..amount] with an infinity sentinel (amount + 1).
  3. For each amount a from 1 to amount:
  • For each coin c in coins:
  • If a - c >= 0: dp[a] = min(dp[a], 1 + dp[a - c])
  1. If dp[amount] > amount, the target cannot be formed; return -1. Otherwise, return dp[amount].

Step-by-step execution walkthrough

1
dp Array Init (amount = 11, coins = [1, 2, 5])

dp of size 12 initialized. dp[0] = 0, all others initialized to infinity (12).

dp[0] = 0, dp[1..11] = 12
2
Compute Small Amounts

dp[1] = 1 (using coin 1). dp[2] = min(1+dp[1], 1+dp[0]) = 1 (using coin 2).

dp[1] = 1, dp[2] = 1
3
Amount 5 and 6

dp[5] = 1 (using coin 5). dp[6] = 1 + dp[6 - 5] = 1 + dp[1] = 2.

dp[5] = 1, dp[6] = 2
4
Amount 11 (Final Result)

dp[11] = 1 + dp[11 - 5] = 1 + dp[6] = 1 + 2 = 3 coins (5 + 5 + 1).

dp[11] = 3 -> Result: 3
Advantages
  • •Optimal O(S * n) runtime
  • •Clean bottom-up array iteration avoiding recursion overhead
Trade-offs
  • •Consumes O(S) auxiliary memory proportional to the target amount

Code Implementations

Copy & paste production-ready solutions for Bottom-Up Dynamic Programming (Tabulation) in your language of choice

File: solution.py
Python
def coin_change(coins: list[int], amount: int) -> int:
    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 else -1
if __name__ == "__main__":
    print("test1 (11):", coin_change([1, 2, 5], 11))
    print("test2 (3):", coin_change([2], 3))
    print("test3 (0):", coin_change([1], 0))
Interactive visualizer available

Understand Complexity Analysis Visually

Analyse algorithm time and space efficiencies using Big O boundary notations. Test live edge cases and watch memory state transitions step-by-step.

Launch Complexity Analysis Visualizer

Frequently Asked Questions

Related Logic & Algorithm Problems

All problems
EasyDynamic Programming
Visualizer

Climbing Stairs

Count the distinct ways to reach the top of an n-step staircase when hopping 1 or 2 steps at a time. The premier gentle introduction to Dynamic Programming and state transition.

1 approach(O(n))
Learn logic
MediumDynamic Programming
Visualizer

Maximum Subarray (Kadane's Algorithm)

Find the contiguous slice of an array that yields the largest sum. Kadane's algorithm demonstrates the art of shedding negative historical baggage in O(n) linear time.

1 approach(O(n))
Learn logic