Understanding The Coin Change Problem With Dynamic Programming | We have input values of N and an array Coins that holds all of the coins . We use data type of because long we want to be able to test large values without integer overflow ; Create the ways array to 1 plus the amount to stop overflow ; Set the first way to 1 because its 0 and there is 1 way to make 0 with 0 coins ; Go through all of the coins ; Make a comparison to each index value of ways with the coin value . ; Update the ways array ; return the value at the Nth position of the ways array . ; Driver code
def getNumberOfWays ( N , Coins ) : NEW_LINE INDENT ways = [ 0 ] * ( N + 1 ) ; NEW_LINE ways [ 0 ] = 1 ; NEW_LINE for i in range ( len ( Coins ) ) : NEW_LINE INDENT for j in range ( len ( ways ) ) : NEW_LINE INDENT if ( Coins [ i ] <= j ) : NEW_LINE INDENT ways [ j ] += ways [ ( int ) ( j - Coins [ i ] ) ] ; NEW_LINE DEDENT DEDENT DEDENT return ways [ N ] ; NEW_LINE DEDENT def printArray ( coins ) : NEW_LINE INDENT for i in coins : NEW_LINE INDENT print ( i ) ; NEW_LINE DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT Coins = [ 1 , 5 , 10 ] ; NEW_LINE print ( " The ▁ Coins ▁ Array : " ) ; NEW_LINE printArray ( Coins ) ; NEW_LINE print ( " Solution : " , end = " " ) ; NEW_LINE print ( getNumberOfWays ( 12 , Coins ) ) ; NEW_LINE DEDENT