Coin Change (Dynamic Programming)

2
votes

We usually the following recurrence relation for the coin change problem: (P is the total money for which we need change and d_i is the coin available)

But can't we make it like this: (V is the given sorted set of coins available, i and j are its subscripts with Vj being the highest value coin given) 

C[p,Vi,j] = C[p,Vi,j-1]     if Vj > p
          = C[p-Vj,Vi,j] + 1  if Vj <=p

Is there anything wrong with what I wrote? Though the solution is not dynamic but isn't it more efficient?

2
algorithmdynamic-programming
Doesn't this assume that V will contain a coin worth 1 unit. What if P = 7 and V = [3, 2], you'd end up getting 2 value 3 coins and then error out instead of 1 value 3 coin and 2 value 2 coins. – Louis Ricci
@LastCoder I got your point. The above solution is assuming that we have a coin worth 1 unit. Now next thing is if we are given coin worth 1 unit, then the above be more efficient solution then the dynamic solution, right? – Gaurav
Where do you use Vi in your formula? – IVlad
@IVlad: The set is actually Vi to Vj. So when I write Vi,j then i assume that the set V contains all the elements from Vi to Vj. When I write Vi,j-1 then I assume that the set V contains all the elements form Vi to Vj-1 which means that last coin is excluded form the coins set. – Gaurav
That is a very confusing notation, because you also use just Vj and you use commas to separate both indices and function parameters. I suggest using square brackets to make it clearer, I read your formula as C[p,(Vi),(j-1)]; C[(p-Vj),(Vi),(j)]. – IVlad

2 Answers

4
votes

Consider P = 6, V = {4, 3, 1}. You would pick 4, 1, 1 instead of 3, 3, so 3 coins instead of the optimal 2.

0
votes

What you've written is similar to the greedy algorithm that works only under certain conditions. (See - How to tell if greedy algorithm suffices for finding minimum coin change?).

Also, in your version you aren't actually using Vi within the recurrence, so it's just a waste of memory