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

3

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:

1. Create a DP array of size amount + 1

2. Initialize all values with a large number

3. Set dp[0] = 0

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

5. If dp[amount] is still large, return -1

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