#### 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'
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;
}```