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?
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
.