Coin Change (Dynamic Programming)

Question

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?

Answer 1

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.

Answer 2

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