Given coins of different denominations and a total amount of money, find the number of combinations that make up that amount. For example, given unlimited coins in 1, 2, 4 denominations, how many combinations are there to make up the amount of 12? Thought ProcessGiven coins in different denominations, we'd solve this problem by breaking it into subproblems which means given coins in less different denominations. The answer to the problem of given coins in n different denominations is based on solving the problem of given coins in (n1) different denominations, and the answer to the problem of coins in (n1) different denominations is based on solving the problem of coins in (n2) different denominations. We can use an array named combination to store the number of combinations that make up the amount. For example, the number of combinations to make up the amount of 1 is stored combination[1], and the combinations to make up the amount of 12 is stored in combination [12]. The number of combinations to make up a given amount is equal to the number of combinations before a coin denomination is added to the picture, plus the number of combinations after such a coin denomination is added to the picture for the amount of "amount  coin". When adding the first coin to the picture, we'd calculate this array  combination. When adding the 2nd coin to the picture, the same combination[amount] is being calculated based on the following pseudocode: for each current coin denomination: This video explains using the array very well: Code SampleNote the trick of initializing the combination[0] to 1 to begin with. [1] references
0 Comments
Leave a Reply. 
Categories
All
Archives
March 2018
