Data Structures and Algorithms (DSA)  

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

3

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:

  1. Create a DP array of size amount + 1

  2. Initialize all values as a very large number (infinity)

  3. Set dp[0] = 0 (0 coins needed to make amount 0)

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

Amountdp value
00
11
21
32
42
51
62
72
83
93
102
113

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.

Membership not found