# Greedy Or Not?

There is a list of coins : $$L = \{100000,10000,1000,100,10,1\}$$

You want to know the minimum number of coins needed to achieve value $$V$$, so you asked the two best programmers in the world, Alice and Bob, and each of them proposed a different algorithm:

Alice [Dynamic Programming] :

 1 2 3 4 5 6 7 8 def dpMakeChange(L, V, minCoins): for cents in range(V+1): coinCount = cents for j in [c for c in L if c <= cents]: if minCoins[cents-j] + 1 < coinCount: coinCount = minCoins[cents-j] + 1 minCoins[cents] = coinCount return minCoins[V]

Bob [Greedy] :

 1 2 3 4 5 6 7 def greedyMakeChange(L, V): minCoin = 0 for change in L: while V >= change: V -= change minCoin += 1 return minCoin

Which is the better algorithm? Of course, correctness is your top priority, then the speed.

×