Dynamic Programming Practice Problems : Cents and Coins

Dynamic Programming Practice Problems : Cents and Coins

Many times its difficult to find solutions to dynamic problems. In this series of posts, I will try to post a few problems on Dynamic programming and provide solution in a way you can understand and write up your own solutions easily.

However, I would suggest you to try solving the problem on your own before jumping into solutions directly.

1. Suppose we want to make change for n cents, using the least number of coins of denominations 1, 10, and 25 cents.[ for example suppose you have to give n cents (say, 89 cents or 56 cents or 39 cents or 12 cents etc or some 30 cents ) to a shopkeeper for purchasing a small item. In your wallet you have only coins of 1, 10 and 25 cents. Now, decide which coins will you give and what should be the solution.]. Describe an O(n) dynamic programming algorithm to find an optimal solution. (There is also an easy O(1) algorithm but the idea here is to illustrate dynamic programming.)

Solution :

• There is a very straightforward O(1) time solution. It can be shown that if n >= 50 then any solution will include a set of coins that adds to exactly 50 cents. Hence it can be shown that an optimal solution uses 2 · floor(n/50) quarters (if we were given 50 cent coins also, we could have taken it as only floor(n/50)) along with an optimal solution for making n/50 − floor(n/50) cents which can be looked up in a table of size 50.

• Following is a dynamic programming algorithm ( that does not use the fact that an optimal solution can be proven to use 2 · floor(n/50) quarters and hence is not as efficient.) The general subproblem will be to make change for i cents for 1 i n. Let c[i] denote the fewest coins needed to make i cents.

c[i] =   use i pennies                                            if  i < 9

• Note that c[n] is the optimal number of coins needed for the original problem.

• Clearly when i < 10 the optimal solution can use only pennies (since that is the only coin available). Otherwise, the optimal solution either uses a dime or a quarter and both of these are considered.

• Finally, the optimal substructure property clearly holds since the final solution just adds one coin to the subproblem solution. There are n subproblems each of which takes O(1) time to solve and hence the overall time complexity is O(n).

 Then we can define c[i] recursively by: 

           OR

          c[i − 10] + 1                                             if 10 <= i < 24
           OR

          min(c[i − 10] + 1, c[i − 25] + 1)                if i <=25