#### Dynamic Programming

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