Recursion: Make Changes With Fewest Coins
Solution 1:
minCoins = change
: minCoins
is initialized with the value of change
which is the maximum value that recMC
can return as the minimum value of a coin is 1, assuming integer values of coins.
if change in coinValueList: return 1
: base case 1 - if some coin has a value of that of change
we just need to grab this 1 coin, thus returning 1
for i in [c for c in coinValueList if c <= change]:
:
The function then loops through all possible values of 1 single coin to
numCoins = 1 + recMC(coinValueList,change-i)
: deduct the coin value i
from change
, add 1 coin to the number of coins needed which is recursively calculated for the leftover change (change-i
). This works inductively from the 2 base cases
if numCoins < minCoins: minCoins = numCoins
inside this loop effectively assigns the smallest number of coins possible to minCoins
If change
still had the initialized value of minCoins
(implying no value c
in coinValueList
satisfies c <= change
), this means that the number of coins needed is also the value of change
, i.e. change
1-unit coins. This is base case 2 that is based on the pre-condition that the coin with value 1 is always available.
Post a Comment for "Recursion: Make Changes With Fewest Coins"