### Given change C and $S=\{S_{1}, S_{2}, ... ,S_{k} \}$, find the mininum numbers of coins that adds up to C

let the numbers of coins to be $\varphi$

### Example 1. Given change C = 6 and $S=\{2, 3, 4\}$, find the mininum number of coins adds up to 6

### C = 6 = 2 + 2 + 2 $\Rightarrow \varphi =3$

### C = 6 = 2 + 4 $\Rightarrow \varphi =2$

### C = 6 = 4 + 2 $\Rightarrow \varphi =2$

### C = 6 = 3 + 3 $\Rightarrow \varphi =2$

### $\Rightarrow \varphi=2$

### Mathematic Concept

### Given C and find the linear combination of $S=\{S_{1}, S_{2}, ... ,S_{k} \} \Rightarrow C = \sum_{i=1}^{k} x_{i}S_{i}$

### $C = 6\quad S=\{2, 3, 4\}$

### $6 = 1*2 + 1*2 + 1*2 \Rightarrow x_{1}=1\quad x_{2}=1\quad x_{3}=1 \Rightarrow \varphi = 1 + 1 + 1 = 3 \textbf{ coins}$

### $6 = 1*2 + 1*4 \Rightarrow x_{1}=1\quad x_{2}=1 \Rightarrow \varphi = 1 + 1 = 2 \textbf{ coins}$

### $6 = 1*4 + 1*2 \Rightarrow x_{1}=1\quad x_{2}=1 \Rightarrow \varphi = 1 + 1 = 2 \textbf{ coins}$

### $6 = 1*3 + 1*3 \Rightarrow x_{1}=1\quad x_{2}=1 \Rightarrow \varphi = 1 + 1 = 2 \textbf{ coins}$

### Example 2. Given change C = 0 and $S=\{2, 3, 4\}$, find the mininum number of coins adds up to 0

### Since C = 0, zero coin adds up to C = 0. Therefore, the solution is zero coin

### C = 0 = 0 $\Rightarrow \varphi =0$

### Mathematic Concept

### $C = 0 = 0*2 + 0*3 + 0*4 \Rightarrow x_{1}=0\quad x_{2}=0\quad x_{3}=0 \Rightarrow \varphi = 0 + 0 + 0 = 0 \textbf{ coin}$

### Example 3. Given change C = -2 and $S=\{2, 3, 4\}$(has no coin), find the mininum number of coins adds up to 6

### There is no solution, since C is negative [ $\because$ we can't have negative number of coins ]

### If C < 0, then we can let $\varphi =\infty$

### Ok, you might ask why is $\varphi =\infty$, why not is $\varphi =0$

### Well, $\varphi =0$ is the solution for C = 0. But I still don't understand why $\varphi$ has to be $\infty$

### Real reason behind that why $\varphi$ has to be $\infty$

### $\infty$ acts as identity for min( , ) operation

### E.g. $0$ is the identity for + since $0 + a = a, a \in \mathbb{N}$

### E.g. $1$ is the identity for * since $1*a = a, a\in \mathbb{N}$

### Similarly, $\infty$ is the identity for $min( , )$ since $min(\infty, a) = a, a \in \mathbb{N}$

### min(,) is called monoid with Math.MAX_VALUE as identity

### Ok, make sence, but why do we need the $\infty$ as identity for the [ coin change problem ]

### Let's look at the following graph for $\text{coin } = \{2, 3, 4\}, S = 6$

### The value of each node $=$ the value of parent node $-$ weight of the edge [ except the root node ]

### Some leaf nodes are $\infty$ since the value of parent node $<$ the weight of edge

### Why we set the value of the node = $\infty$ ? since we know the path contains $\infty$ can't be a solution

### The only path might be a solution is the value of leaf node has to be zero [ which is the red node ]

### Since we are looking for the minimum number of coins, then the solution(s) has/have to be the shortest path from the root

// /Users/cat/myfile/bitbucket/java/CoinChange.java
//CoinChange.java
//Given coin{2, 3, 4} and s = 6
//Find the minimum number of coins sums up to s
public static int minCount(int[] coin, int s, int k) {
int min = Integer.MAX_VALUE;
if(s == 0)
min = 0;
else if(s > 0) {
// min(s) = min(s-coin[k]) + 1
for(int i=0; i < k; i++) {
int childMin = minCount(coin, s-coin[i], k);
if(childMin != Integer.MAX_VALUE)
min = Math.min(min, childMin + 1);
}
}
return min;
}

Coin Change, 2018 version in Java

/*
(4) -> (4 - 2) -> (2 - 2)
{2} s = 4
[ s=4
[ s=2
[ s = 0
0 <-]
1 <-]
2 <-]
*/
public static int minCoins(List list, int s){
int min = Integer.MAX_VALUE;
if( list != null){
if (s < 0){
return Integer.MAX_VALUE;
}
else if( s == 0){
return 0;
}else{
for(Integer n : list){
min = Math.min(min, minCoins(list, s - n));
}
}
}
return min + 1;
}