Coin Change Problem in Dynamic Programming (DSA)

Introduction

The Coin Change Problem is one of the most popular Dynamic Programming (DP) questions in DSA interviews. It is frequently asked because it tests your understanding of optimal substructure, overlapping subproblems, and decision-making using DP.

In simple words, the problem asks:

Given some coin denominations, how can we form a target amount using the minimum number of coins?

This article explains the Coin Change problem in very simple language, step by step, making it easy for beginners and useful for interview preparation.

What is the Coin Change Problem?

You are given:

An array coins[] representing different coin denominations
An integer amount representing the target value

Your task is to find the minimum number of coins required to make the given amount.

If the amount cannot be formed using the given coins, return -1.

Example

coins = [1, 2, 5]
amount = 11

Output

Explanation

We can form 11 using:

5 + 5 + 1 = 11

Minimum number of coins required = 3

Why Greedy Approach Does Not Always Work

A greedy approach always tries to take the largest coin first.

This may work in some cases, but not always.

Example Where Greedy Fails

coins = [1, 3, 4]
amount = 6

Greedy approach:

4 + 1 + 1 = 3 coins

Optimal solution:

3 + 3 = 2 coins

So, we need a better approach — Dynamic Programming.

Dynamic Programming Approach (Core Idea)

Dynamic Programming helps us solve the problem by building solutions for smaller amounts and using them to solve bigger amounts.

DP State Definition

Let:

dp[i] = minimum number of coins needed to make amount i

Our final answer will be dp[amount].

Step-by-Step DP Explanation

Steps:

Create a DP array of size amount + 1
Initialize all values as a very large number (infinity)
Set dp[0] = 0 (0 coins needed to make amount 0)
For each amount from 1 to target:
- Try every coin
- Update minimum coins required

DP Formula (Easy to Understand)

For every amount i and every coin c:

dp[i] = min(dp[i], dp[i - c] + 1)

This means:

If we take coin c, then we need 1 + coins needed for (i - c)

Dry Run Example

Coins: [1, 2, 5], Amount = 11

Amount	dp value
0	0
1	1
2	1
3	2
4	2
5	1
6	2
7	2
8	3
9	3
10	2
11	3

Final Answer = 3

Code Implementation

C++ Code

int coinChange(vector<int>& coins, int amount) {
    vector<int> dp(amount + 1, amount + 1);
    dp[0] = 0;

    for (int i = 1; i <= amount; i++) {
        for (int coin : coins) {
            if (coin <= i) {
                dp[i] = min(dp[i], dp[i - coin] + 1);
            }
        }
    }

    return dp[amount] > amount ? -1 : dp[amount];
}

Java Code

public int coinChange(int[] coins, int amount) {
    int[] dp = new int[amount + 1];
    Arrays.fill(dp, amount + 1);
    dp[0] = 0;

    for (int i = 1; i <= amount; i++) {
        for (int coin : coins) {
            if (coin <= i) {
                dp[i] = Math.min(dp[i], dp[i - coin] + 1);
            }
        }
    }

    return dp[amount] > amount ? -1 : dp[amount];
}

Python Code

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

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

    return -1 if dp[amount] > amount else dp[amount]

Time and Space Complexity

Time Complexity: O(n × amount), where n is number of coins
Space Complexity: O(amount)

This is efficient and acceptable for interviews.

Important Edge Cases

Amount is 0
No coins given
Amount cannot be formed using coins

Always mention these in interviews.

Common Interview Variations

Coin Change – number of ways
Unlimited vs limited coins
Minimum coins with constraints
Space optimized solution

Understanding this problem helps solve many DP variations.

Summary

The Coin Change Problem is a classic Dynamic Programming question that teaches how to build solutions using smaller subproblems. Greedy approaches fail in many cases, but DP guarantees the optimal solution. By understanding the DP state, transition, and base case, you can confidently solve this problem and many related optimization problems in coding interviews.