[Math] Dynamic programming:Making a Change

algorithmsdynamic programmingrecursive algorithms

I'm practicing problems on dynamic programming.The problem is as follows:

You are given n types of coin denominations of values v(1) < v(2) < … < v(n) (all integers). Assume v(1) = 1, so you can always make change for any amount of
money C. Give an algorithm which makes change for an amount of money C with as
few coins as possible.

Here is the solution which i have figured out..

So,the idea is to make a change such that we need fewer coins in making that be it of any denomination.

So,this is all about choices…
If i need for 1 dollar i have one option i.e to select v1 —–> (1) this is an option

If for example ,we are making a change for 10 dollars

     --->pick ten 'one' dollar notes
     ---->pick two  'five dollar notes
     ----->pick a  'ten' dollar note itself..

we need to calculate the minimum of these choices and return it as our
solution.

Is the approach i'm following is correct?

Best Answer

Trying all possible solutions is an exhaustive search. The following is a dynamic programming algorithm. The minimal solution we search for can be defined recursively:

if m=v(k), for a k, then:
    coins_needed(m):=1, 
otherwise:   
    coins_needed(m):=
        min(coins_needed(1)+coins_needed(m-1),
        coins_needed(2)+coins_needed(m-2),
        ...,
        coins_needed(floor(m/2)+coins_needed(ceiling(m/2)))

One can start with m=1 and , then calculate coins_needed for m=2 and so on. It is important to store all the minimal solution one has calculated so far, otherwise the algorithm needs an exponential running time.

If one has calculated coins_needed(m-1) in this way, one has already calculated coins_needed(1),...,coins_needed(m-2) and stored the results. It is now easy to calculate coins(m) according to the above formula.

It is dynamic programming as defined in Wikipedia, The problem has optimal substructure, because the problem solution can be constructed of the solution of the smaller subproblems, and each subproblem can be broken in smaller sub problems again but we have overlapping subproblems. This means we have always the same sub problems that can be reused. So if we store the results of the subproblems (memoization) we can reuse them.

Related Question