Find minimum number of coins that make a given value | 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 Code
< ? php function minCoins ( $ coins , $ m , $ V ) { $ table [ $ V + 1 ] = array ( ) ; $ table [ 0 ] = 0 ; for ( $ i = 1 ; $ i <= $ V ; $ i ++ ) $ table [ $ i ] = PHP_INT_MAX ; for ( $ i = 1 ; $ i <= $ V ; $ i ++ ) { for ( $ j = 0 ; $ j < $ m ; $ j ++ ) if ( $ coins [ $ j ] <= $ i ) { $ sub_res = $ table [ $ i - $ coins [ $ j ] ] ; if ( $ sub_res != PHP_INT_MAX && $ sub_res + 1 < $ table [ $ i ] ) $ table [ $ i ] = $ sub_res + 1 ; } } if ( $ table [ $ V ] == PHP_INT_MAX ) return -1 ; return $ table [ $ V ] ; } $ coins = array ( 9 , 6 , 5 , 1 ) ; $ m = sizeof ( $ coins ) ; $ V = 11 ; echo " Minimum ▁ coins ▁ required ▁ is ▁ " , minCoins ( $ coins , $ m , $ V ) ; ? >