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
#include <bits/stdc++.h> NEW_LINE using namespace std ; long getNumberOfWays ( long N , vector < long > Coins ) { vector < long > ways ( N + 1 ) ; ways [ 0 ] = 1 ; for ( int i = 0 ; i < Coins . size ( ) ; i ++ ) { for ( int j = 0 ; j < ways . size ( ) ; j ++ ) { if ( Coins [ i ] <= j ) { ways [ j ] += ways [ ( j - Coins [ i ] ) ] ; } } } return ways [ N ] ; } void printArray ( vector < long > coins ) { for ( long i : coins ) cout << i << " STRNEWLINE " ; } int main ( ) { vector < long > Coins = { 1 , 5 , 10 } ; cout << " The ▁ Coins ▁ Array : " << endl ; printArray ( Coins ) ; cout << " Solution : " << endl ; cout << getNumberOfWays ( 12 , Coins ) << endl ; }