Coin Change problem [Leetcode322]

The Coin Change problem can be solved using various algorithms such as Dynamic Programming, Recursion, or even Greedy algorithms for specific scenarios. Below is a Java implementation using Dynamic Programming:

The problem is to find the minimum number of coins needed to make up a given value, assuming you have an array of coin denominations.

public class CoinChange {

  public static int minCoins(int[] coins, int amount) {
    int[] dp = new int[amount + 1];

    // Initialize dp array. We use Integer.MAX_VALUE - 1 to avoid integer overflow
    for (int i = 1; i <= amount; i++) {
      dp[i] = Integer.MAX_VALUE - 1;
    }

    // Base case: 0 coins are needed to make the amount 0
    dp[0] = 0;

    // Build up the dp array in bottom-up fashion
    for (int i = 1; i <= amount; i++) {
      for (int coin : coins) {
        if (i - coin >= 0) {
          dp[i] = Math.min(dp[i], dp[i - coin] + 1);
        }
      }
    }

    return dp[amount] == Integer.MAX_VALUE - 1 ? -1 : dp[amount];
  }

  public static void main(String[] args) {
    int[] coins = {1, 2, 5};
    int amount = 11;
    int result = minCoins(coins, amount);
    if (result == -1) {
      System.out.println("No solution exists");
    } else {
      System.out.println("Minimum coins needed: " + result);
    }
  }
}

In this example, the minCoins function uses dynamic programming to find the minimum number of coins required to make the amount. The array dp is initialized with Integer.MAX_VALUE - 1 (to avoid overflow when adding 1). The value at dp[i] will eventually contain the minimum number of coins needed to make the amount i.

The function iterates through the dp array, updating dp[i] based on smaller sub-problems (dp[i - coin] + 1). Finally, dp[amount] will contain the minimum number of coins needed to form the amount.

If it’s not possible to form the amount with the given coins, the function returns -1.

Problem Source: https://leetcode.com/problems/coin-change/