Coin Change Problem

The Coin Change Problem is a classic problem in computer science where we need to find the minimum number of coins required to make a given amount of money.

For example, suppose we have the following coins:

• 1 cent
• 2 cents
• 5 cents

And we want to make a total of 11 cents. To find the minimum number of coins required, we can use a dynamic programming approach.

We can create an array dp of size amount + 1 and initialize all the values to amount + 1. This will act as our memoization table, storing the minimum number of coins required for each amount from 0 to amount.

We then iterate through the array of coins and for each coin, iterate through all the amounts from coin to amount. For each amount i, we update dp[i] with the minimum of its current value and dp[i - coin] + 1 (where dp[i - coin] represents the minimum number of coins required to make the remaining amount after subtracting the coin).

Finally, the value at dp[amount] represents the minimum number of coins required to make the given amount. If the value is greater than the amount, it means it is not possible to make the amount using the given coins.

Here's the Java code to solve the Coin Change Problem using dynamic programming:

1import java.util.Arrays;
2
3class CoinChangeProblem {
4  public static int coinChange(int[] coins, int amount) {
5    int[] dp = new int[amount + 1];
6    Arrays.fill(dp, amount + 1);
7    dp[0] = 0;
8
9    for (int coin : coins) {
10      for (int i = coin; i <= amount; i++) {
11        dp[i] = Math.min(dp[i], dp[i - coin] + 1);
12      }
13    }
14
15    return dp[amount] > amount ? -1 : dp[amount];
16  }
17
18  public static void main(String[] args) {
19    int[] coins = {1, 2, 5};
20    int amount = 11;
21    int result = coinChange(coins, amount);
22    System.out.println("Minimum number of coins required: " + result);
23  }
24}

xxxxxxxxxx

import java.util.Arrays;

​

class CoinChangeProblem {

  public static int coinChange(int[] coins, int amount) {

    int[] dp = new int[amount + 1];

    Arrays.fill(dp, amount + 1);

    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];

  }

​

  public static void main(String[] args) {

    int[] coins = {1, 2, 5};

    int amount = 11;

    int result = coinChange(coins, amount);

    System.out.println("Minimum number of coins required: " + result);

  }

}