Coin Change Problem in Dynamic Programming (DSA)

Introduction

The Coin Change Problem is a classic and very important Dynamic Programming (DP) problem in DSA. It is frequently asked in coding interviews because it tests your understanding of optimization, decision making, and DP table construction.

In simple words, this problem is about finding the minimum number of coins needed to make a given amount using the available coin denominations.

This article explains the Coin Change problem in very simple, human-friendly language, starting from the basics and progressing to interview-level understanding.

What is the Coin Change Problem?

You are given:

An array of coin denominations
A target amount

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

Important rules:

You can use each coin any number of times
If it is not possible to make the amount, return -1

Example

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

Output

Explanation

The minimum number of coins needed to make 11 is:

5 + 5 + 1 = 11

So the answer is 3 coins.

Why Greedy Approach Does Not Always Work

A greedy approach always picks the largest coin first.

This may work for some cases but fails for others.

Example Where Greedy Fails

Coins = [1, 3, 4]
Amount = 6

Greedy picks:

4 + 1 + 1 = 3 coins

But optimal solution is:

3 + 3 = 2 coins

So we need a better approach.

Why Dynamic Programming is Needed

Dynamic Programming helps us:

Break the problem into smaller subproblems
Store results to avoid recomputation
Find the optimal solution efficiently

This makes DP the best choice for the Coin Change problem.

Dynamic Programming Approach (Core Idea)

DP State Definition

We create a DP array where:

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

Base Case

dp[0] = 0 (0 coins are needed to make amount 0)

All other values are initialized to a large number.

Step-by-Step DP Explanation

Steps:

Create a DP array of size amount + 1
Initialize all values with a large number
Set dp[0] = 0
For each amount from 1 to target amount:
- Try every coin
- If coin value ≤ current amount:
  - Update dp[current] = min(dp[current], dp[current - coin] + 1)
If dp[amount] is still large, return -1
Otherwise, return dp[amount]

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(amount × number of coins)
Space Complexity: O(amount)

This solution is efficient for typical interview constraints.

Important Edge Cases

Amount is 0
Coins array is empty
Amount cannot be formed using given coins

These cases should always be discussed in interviews.

Common Interview Variations

Count number of ways to make the amount
Coin Change using recursion + memoization
Limited number of coins
Print the coins used

Understanding this problem helps solve many DP variations.

Summary

Building secure web applications is essential for protecting users and maintaining trust. ASP.NET Core provides a comprehensive set of tools for implementing authentication, authorization, data validation, and defenses against common web attacks. By following best practices such as enforcing HTTPS, validating inputs, and securing sensitive endpoints, developers can significantly reduce security risks and build resilient applications.

Staying informed about evolving security threats and continuously applying best practices is key to long-term application security.