**Problem :- **

**Coin Change** problem.

Given a set of **coin denominations**, find the minimum number of coins required to make a change

for a **target value**.

Consider a set of denominations as **{ 1, 2, 5, 9 }**.

Suppose we want to make a change for a target value = **13**.

There are many possible ways like using

13 coins of denomination **1** ( Total **13** coins )

6 coins of denomination **2** & **1** coin of denomination **1** ( Total **7** coins )

2 coins of denomination **5** with 1 coin each of denomination **1** & **2** ( Total **4** coins )

**Minimum no. of coins = 3** ( 1 coin of denomination **9**, 2 coins of denomination **2** )

**Solution :- **

Suppose we are given an array **value [ n ]** which stores coins of **n** denominations.

We will maintain an array **change [ n + 1 ]** where index **j** of the array stores the minimum number of coins required
to make a change for value **j**. Eventually, **change [ x ]** will give the solution ( minimum no. of coins required to
make a change for target value **x** ).

Let us find the structure of the optimal solution.

Let **change ( j )** denotes the minimum number of coins required to make a change for value **' j '**.

Now, to achieve that, we need to decide whether to consider a coin of particular denomination.

So, we will iterate through the array **value [ n ]** and either choose or reject a coin.
If we choose a coin of denomination **i** , then the problem reduces to **1 + ( No. of coins to make a change for ' j - value ( i ) ' )**

Since, our objective is to find minimum no. of coins required to make a change for value **j**,

we will consider every possible denomination **i** ( i =
0, 1, ... n ) and find the **minimum (** 1 + ( No. of coins to make a change for **' j - value ( i ) '** ) **)** for all values of **' i '**.

Thus, the structure of the optimal solution is defined recursively as :

**change ( j ) = min [ ( 1 + change ( j - values [ i ] ) ) for i = 0 , 1 , ... , n ]**

**change ( x )** is the required solution.

**#include<iostream>**
**using namespace** std;
**#define INF 9999** *// denotes a very high value
/* given a set of coin denomination, find the min no. of coins required
to make a change for a target value.
suppose, we are given 'n' denominations in an array 'values' and
change(j) -> min no. of coins required to make a change for value 'j'
then change(target) -> required answer
So we need to create a temporary array change[0...target] where index 'j'
stores the min no. of coins required to make a change for value j
Standard Recursive Solution :-
change[j] = min[ ( 1 + change[j-values[i]] ) for i = 0...n-1 ]
*/*
**int** minCoins(**int** values[],**int** n,**int** target) {
*// array to store the min no. of coins required to make a change
// for each index 0...target*
**int** change[target+1];
change[0] = 0;
**int** i,j;
**for**(j=1;j<=target;j++) {
**int** min = INF;
*// as per the recursive solution for all i = {0...n-1} *
**for**(i=0;i<n;i++) {
**if**(j>=values[i] && (change[j-values[i]]+1) < min)
min = change[j-values[i]]+1;
}
*// store the minimum no. of coins required to make a change for target = j*
change[j] = min;
}
**return** change[target];
}
*//main*
**int** main() {
**int** values[] = {1,2,5,9};
**int** n = **sizeof**(values)/**sizeof**(values[0]);
**int** target = 13;
**int** min = minCoins(values,n,target);
cout<<"\nMin no. of coins required :: "<<min;
cout<<endl;
}