Coin Change

DSA · Dynamic Programming

Theory

Coin change has two classic forms. Minimum coins: dp[a] is the fewest coins making amount a, computed as 1 + min(dp[a - coin]) over all coins. Number of ways: dp[a] counts combinations, adding dp[a - coin] while looping over coins on the outside so each combination is counted once. Both run in O(amount × number of coins) and work for any coin system, unlike greedy.

Why we use it

It shows how DP fixes problems where greedy fails and is a very common interview question.

When to use it

Use it for making change, counting ways to reach a score, unbounded knapsack and resource combination problems.

How it works

  1. dp[0] = 0, others infinity
  2. For amount a = 1..target
  3. For each coin c <= a: dp[a] = min(dp[a], dp[a - c] + 1)
  4. dp[target] is infinity? Yes: Return -1. No: Return dp[target].

Syntax

Minimum coins:
dp = [0] + [inf] * amount
for a in 1..amount: dp[a] = min(dp[a-c] + 1 for c in coins if c <= a)

Number of ways:
ways = [1] + [0] * amount
for c in coins: for a in c..amount: ways[a] += ways[a-c]

Example

def min_coins(coins, amount):
    dp = [0] + [float("inf")] * amount
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a and dp[a - c] + 1 < dp[a]:
                dp[a] = dp[a - c] + 1
    return dp[amount] if dp[amount] != float("inf") else -1

def count_ways(coins, amount):
    ways = [1] + [0] * amount
    for c in coins:
        for a in range(c, amount + 1):
            ways[a] += ways[a - c]
    return ways[amount]

print("Min coins for 6 with [1,3,4]:", min_coins([1, 3, 4], 6))
print("Min coins for 11 with [2]:", min_coins([2], 11))
print("Ways to make 10 with [1,2,5]:", count_ways([1, 2, 5], 10))

Key points

DSA topics

Introduction to DSA

Arrays and Searching

Sorting Algorithms

Linked Lists

Stacks and Queues

Hashing

Trees

Heaps

Graphs

Algorithm Techniques

Classic Algorithms

Dynamic Programming

T
Tech Town
Log InSign Up Free
Home SQL Python DSA Power BI Snowflake Databricks Spark Gen AI Practice Problems Contest Blog

Data Structures & Algorithms

The complete DSA roadmap: theory, why and when to use every structure and algorithm, Big O complexity, and Python code you can run right here in the browser.

{{ sectionCount }}
Sections
{{ topicCount }}
Topics
Free
Forever
Hands-on practice Practice DSA Online 251 problems across 13 patterns, with hidden tests and step-by-step optimal solutions. Start practising →
Section {{ sec.num }}

{{ sec.label }}

DSA  /  {{ current.sectionLabel }}  /  {{ current.name }}

{{ current.name }}

Theory

{{ current.def }}

Why we use it

{{ current.why }}

When to use it

{{ current.when }}

Flowchart — how {{ current.name }} works
{{ nd.text }}
{{ nd.text }}
◇ {{ nd.text }}
Yes → {{ nd.yes }}
No → {{ nd.no }}
Step-by-step visualisation
{{ cell.v }}
{{ cell.i }} {{ cell.tag }}
Step {{ vizStepLabel }}: {{ vizNote }}
■ comparing ■ swapping / moving ■ done / found ■ out of range
Complexity & Pseudocode
{{ current.syntax }}
Example Code
{{ current.example }}
▶ Try It Live — runs real Python 3 in your browser (first run loads the engine)
{{ liveOutput }}
{{ liveError }}
Key Points — click to check off as you learn
  • {{ pt.mark }} {{ pt.text }}

Share this topic