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 long because 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
function getNumberOfWays ( N , Coins ) { let ways = new Array ( N + 1 ) ; for ( let i = 0 ; i < N + 1 ; i ++ ) { ways [ i ] = 0 ; } ways [ 0 ] = 1 ; for ( let i = 0 ; i < Coins . length ; i ++ ) { for ( let j = 0 ; j < ways . length ; j ++ ) { if ( Coins [ i ] <= j ) { ways [ j ] += ways [ ( j - Coins [ i ] ) ] ; } } } return ways [ N ] ; } function printArray ( coins ) { for ( let i = 0 ; i < coins . length ; i ++ ) { document . write ( coins [ i ] + " " ) ; } } let Coins = [ 1 , 5 , 10 ] ; document . write ( " " ) ; printArray ( Coins ) ; document . write ( " " ) ; document . write ( getNumberOfWays ( 12 , Coins ) + " " ) ;