# Coin Change Problems

In this article, you will learn to analyze and resolve the Coin change problems by using a Dynamic programming algorithm

## Problem 1: Count ways of coin change

- Given a set of infinite coins
- Find the number of ways to making change for a specific amount of money, without considering the order of the coins

## Example 1

- Input: given a set of infinite coins {2, 3, 1}. Find the number of ways to making change for 4
- Expected output: 4
- Explanation: those 4 ways are {1, 1, 1, 1}, {1, 1, 2}, {1, 3} and {2, 2}

## Approach 1: Dynamic programming

- To making change for a value
`j`

, need to use coins with a value less than or equal to`j`

- For each coin in the set
`c[i]`

, calculate the ways of making change`w[j] = w[j] + w[j - c[i]]`

with`c[i] <= j <= target`

,`w[0] = 1`

is base case,`w[target]`

is the final result

```
package com.hellokoding.algorithm;
import java.util.Arrays;
public class DP_CoinChange {
static int countWays(int[] coins, int targetCoinChange) {
int[] wayOfCoinChanges = new int[targetCoinChange+1];
wayOfCoinChanges[0] = 1;
for (int i = 0; i < coins.length; i++) {
for (int j = coins[i]; j <= targetCoinChange; j++) {
wayOfCoinChanges[j] += wayOfCoinChanges[j - coins[i]];
}
System.out.println(Arrays.toString(wayOfCoinChanges));
}
return wayOfCoinChanges[targetCoinChange];
}
public static void main(String[] args) {
System.out.println(countWays(new int[]{2, 3, 1}, 4));
}
}
```

- Time complexity: O(nm) with n is the change target, m is the number of coins
- Space complexity: O(n) with n is the change target

## Problem 2: Minimum coin change

- 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 2

- 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}

## Approach 2: Dynamic programming

- 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] = 0`

is base case,`m[target]`

is the final result

```
package com.hellokoding.algorithm;
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] = 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: O(nm) with n is the change target, m is the number of coins
- Space complexity: O(n) with n is the change target