In this article, we will learn to resolve the Coin Change problem in Java by using a dynamic programming algorithm

## Problem

• Given a set of infinite coins

• Find the minimum number of coins to making change for a specific amount of money, without considering the order of the coins

## Example

• Input: given a set of infinite coins {2, 3, 1}. Find the minimum number of coins of making change for 3

• Expected output: 1

• Explanation: there're 3 ways to making change for 3: {3}, {1, 1, 1}, {1, 2}, minimum is {3}

## Dynamic Programming Approach

• To making change for a value `i`, need to use coins with a value less than or equal to `i`

• For each coin in the set `c[j]`, calculate the minimum number of coins to making change `m[i] = Math.min(m[i], m[i - c[j]]) + 1` with `c[j] <= i <= target`, `m = 0` is base case, `m[target]` is the final result

``````import java.util.Arrays;

public class DP_CoinChange2 {
static int countMin(int[] coins, int targetCoinChange) {
int[] minNoOfCoins = new int[targetCoinChange+1];
Arrays.fill(minNoOfCoins, targetCoinChange + 1);

minNoOfCoins = 0;

for (int i = 1; i <= targetCoinChange; i++) {
for (int j = 0; j < coins.length; j++) {
if (coins[j] <= i) {
minNoOfCoins[i] = Math.min(minNoOfCoins[i], minNoOfCoins[i - coins[j]] + 1);
}
}
}

return minNoOfCoins[targetCoinChange] > targetCoinChange ? -1 : minNoOfCoins[targetCoinChange];
}

public static void main(String[] args) {
System.out.println(countMin(new int[]{2, 3, 1}, 3));
}
}
``````
• Time complexity is O(nm) and space complexity is O(n) where n is the change target, m is the number of coins