Find minimum number of coins that make a given value | A Dynamic Programming based Python3 program to find minimum of coins to make a given change V ; m is size of coins array ( number ofdifferent 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
import sys NEW_LINE def minCoins ( coins , m , V ) : NEW_LINE INDENT table = [ 0 for i in range ( V + 1 ) ] NEW_LINE table [ 0 ] = 0 NEW_LINE for i in range ( 1 , V + 1 ) : NEW_LINE INDENT table [ i ] = sys . maxsize NEW_LINE DEDENT for i in range ( 1 , V + 1 ) : NEW_LINE INDENT for j in range ( m ) : NEW_LINE INDENT if ( coins [ j ] <= i ) : NEW_LINE INDENT sub_res = table [ i - coins [ j ] ] NEW_LINE if ( sub_res != sys . maxsize and sub_res + 1 < table [ i ] ) : NEW_LINE INDENT table [ i ] = sub_res + 1 NEW_LINE DEDENT DEDENT DEDENT DEDENT if table [ V ] == sys . maxsize : NEW_LINE INDENT return - 1 NEW_LINE DEDENT return table [ V ] NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT coins = [ 9 , 6 , 5 , 1 ] NEW_LINE m = len ( coins ) NEW_LINE V = 11 NEW_LINE print ( " Minimum ▁ coins ▁ required ▁ is ▁ " , minCoins ( coins , m , V ) ) NEW_LINE DEDENT