Coin Change - Java Solution

1. Introduction

In this post, we tackle the "Coin Change" problem, a fundamental problem in dynamic programming. The challenge involves finding the minimum number of coins needed to make up a specific amount of money, given coins of different denominations. This problem is a classic example of making optimal choices to reach a desired outcome.

Problem

Given an array coins representing different coin denominations and an integer amount representing a total amount of money, the task is to determine the fewest number of coins needed to make up that amount. If it is not possible to make up the amount with the given coins, return -1. It is assumed that there is an infinite supply of each coin denomination.

2. Solution Steps

1. Use dynamic programming to solve the problem.

2. Create an array dp of size amount + 1 to store the minimum number of coins needed for each amount from 0 to amount.

3. Initialize each element in dp to a maximum value, and set dp[0] to 0.

4. Iterate through each coin, and for each coin, update the dp array for all amounts that can be reached using that coin.

5. For each amount i, if i - coin is reachable, update dp[i] to the minimum of its current value and dp[i - coin] + 1.

6. After processing all coins, if dp[amount] is still at its maximum value, return -1, otherwise, return dp[amount].

3. Code Program

public class CoinChange {
    public static void main(String[] args) {
        int[] coins = {1, 2, 5};
        int amount = 11;
        System.out.println(coinChange(coins, amount)); // Test the function
    }

    // Function to find the fewest number of coins needed to make up the amount
    public static int coinChange(int[] coins, int amount) {
        int max = amount + 1;
        int[] dp = new int[max];
        Arrays.fill(dp, max);
        dp[0] = 0;

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

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

Output:

3

Explanation:

1. coinChange: This function computes the minimum number of coins required to make up a given amount using coins of various denominations.

2. It initializes a dynamic programming array dp, where dp[i] represents the minimum number of coins needed to make up amount i.

3. The function iterates over each coin and updates dp[i] for all amounts that can be made using that coin. This is done by checking if the current amount minus the coin value is reachable and, if so, updating the minimum number of coins needed.

4. After processing, if dp[amount] is still at its initialized maximum value, it means the amount cannot be made up with the given coins, and the function returns -1. Otherwise, it returns the value of dp[amount].

5. This approach ensures that the problem is solved optimally by iteratively building up the solution for each amount, considering each coin denomination.