Find minimum number of coins that make a given value | A Dynamic Programming based C ++ program to find minimum of coins to make a given change V ; m is size of coins array ( number of different coins ) ; table [ i ] will be storing the minimum number of coins required for i value . So table [ V ] will have result ; Base case ( If given value V is 0 ) ; Initialize all table values as Infinite ; Compute minimum coins required for all values from 1 to V ; Go through all coins smaller than i ; Driver program to test above function
#include <bits/stdc++.h> NEW_LINE using namespace std ; int minCoins ( int coins [ ] , int m , int V ) { int table [ V + 1 ] ; table [ 0 ] = 0 ; for ( int i = 1 ; i <= V ; i ++ ) table [ i ] = INT_MAX ; for ( int i = 1 ; i <= V ; i ++ ) { for ( int j = 0 ; j < m ; j ++ ) if ( coins [ j ] <= i ) { int sub_res = table [ i - coins [ j ] ] ; if ( sub_res != INT_MAX && sub_res + 1 < table [ i ] ) table [ i ] = sub_res + 1 ; } } if ( table [ V ] == INT_MAX ) return -1 ; return table [ V ] ; } int main ( ) { int coins [ ] = { 9 , 6 , 5 , 1 } ; int m = sizeof ( coins ) / sizeof ( coins [ 0 ] ) ; int V = 11 ; cout << " Minimum ▁ coins ▁ required ▁ is ▁ " << minCoins ( coins , m , V ) ; return 0 ; }