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
class getWays { static long getNumberOfWays ( long N , long [ ] Coins ) { long [ ] ways = new long [ ( int ) N + 1 ] ; ways [ 0 ] = 1 ; for ( int i = 0 ; i < Coins . length ; i ++ ) { for ( int j = 0 ; j < ways . length ; j ++ ) { if ( Coins [ i ] <= j ) { ways [ j ] += ways [ ( int ) ( j - Coins [ i ] ) ] ; } } } return ways [ ( int ) N ] ; } static void printArray ( long [ ] coins ) { for ( long i : coins ) System . out . println ( i ) ; } public static void main ( String args [ ] ) { long Coins [ ] = { 1 , 5 , 10 } ; System . out . println ( " The ▁ Coins ▁ Array : " ) ; printArray ( Coins ) ; System . out . println ( " Solution : " ) ; System . out . println ( getNumberOfWays ( 12 , Coins ) ) ; } }