How to Solve the Coin Change Problem

Introduction

The Coin Change Problem is a classic dynamic programming problem in computer science. It challenges us to determine the number of ways to make a specific amount using a given set of coin denominations, or to find the minimum number of coins needed. This problem is widely used to understand recursion, memoization, and bottom-up dynamic programming techniques.

Problem Statement

Given an array of coin denominations and a total amount, determine the minimum number of coins required to make that amount. If it’s not possible to make the amount using the given coins, return -1.

Approach

A dynamic programming solution is typically used to solve this problem efficiently. We create an array where each index represents the minimum number of coins needed to form that amount. Starting from 0 up to the target amount, we build our solution incrementally. This bottom-up strategy ensures that every sub-problem is solved only once and stored for future use.

Java Implementation

Here is an implementation of the minimum coin change solution in Java using a bottom-up dynamic programming approach:

public class CoinChange {

    public static int minimumCoins(int[] coins, int amountRequired) {
        int max = amountRequired + 1;
        int[] dbArr = new int[amountRequired + 1];

        for (int i = 0; i <= amountRequired; i++) {
            dbArr[i] = max;
        }
        dbArr[0] = 0;

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

        return dbArr[amountRequired] > amountRequired ? -1 : dbArr[amountRequired];
    }

    public static void main(String[] args) {
        int[] coins = {1, 2, 5};
        int amount = 11;

        int result = minimumCoins(coins, amount);
        if (result != -1) {
            System.out.println("Minimum coins required: " + result);
        } else {
            System.out.println("Amount cannot be formed with given coins.");
        }
    }
}

Example Explanation

In the given example, we use the coin denominations {1, 2, 5} to make the amount 11. The optimal solution uses three coins: 5 + 5 + 1, so the program outputs 3. The algorithm tests every amount up to 11 and chooses the combination with the fewest coins at each step.

Time and Space Complexity

The time complexity of this algorithm is O(n * amount), where n is the number of coin denominations. The space complexity is O(amount) due to the single-dimensional dp array used to store subproblem results.

Conclusion

The Coin Change Problem illustrates the power of dynamic programming in solving optimization problems. By breaking the problem into smaller subproblems and building up the solution, we can efficiently compute the result, even for larger inputs. This Java implementation provides a clear and effective solution to finding the minimum number of coins required to reach a given amount.

You can find the example code on Github.