Given a set of denominations and an amount, how do we minimize the number of coins to make up the given amount?

Let us consider the set of denominations {1,3,4}. Also assume that we have infinite supply of coins for each denomination. To make change for 6, we can have three combinations

{1,1,4}

{1,1,1,3}

{3,3}

The minimum number of coins to make change for 6 is ‘

**2**‘.This problem can be efficiently solved using dynamic programming approach. Let us formulate the problem in terms of it’s sub-problems.

Let the amount be T and the given denominations are {d

_{1},d_{2},…d_{n}}. Create an array of size (T+1) denoted by MC[].MC[K] denotes the minimum number coins required for amount K. It can be defined as follows

Min{ MC[K-d_{1}], MC[K-d_{2}],…MC[K-d_{n}] } + 1

This means that we can find the solution of a problem from it’s sub-problems and it has optimal sub-structure property suggesting the dynamic programming solution.

Following is the C++ implementation of the above algorithm.