Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Used dynamic programming and memoization solution in Clear category for Making Change by kkkkk
# Borrowed/modified code from this site:
# http://ice-web.cc.gatech.edu/ce21/1/static/audio/static/pythonds/Recursion/DynamicProgramming.html
def checkio(price, denominations):
"""Return the minimum number of coins that add up to the price."""
# Storage for the number of coins needed to reach each cent up to
# the given price.
coin_count = [0] * (price + 1)
# For each cent leading up to the given price ...
for cents in range(1, price + 1):
min_num_of_coins = cents
# For all coins that will work for the current number of cents ...
for coin in [c for c in denominations if c <= cents]:
# Determine the cents needed to make up the difference between
# the current coin and the desired 'cents'. Using that difference,
# lookup the number of coins needed for that amount as found in
# 'coin_count'. Add one more to that count to account for the
# current coin.
#
# If that number of coins is less than the mininum number of
# coins found so far, make that the new minumum number of coins.
if coin_count[cents - coin] + 1 < min_num_of_coins:
min_num_of_coins = coin_count[cents - coin] + 1
# Store the minimun number of coins for this cent value so if
# can be used further along in the price range.
coin_count[cents] = min_num_of_coins
# If no coins could be applied to the price, return None.
if coin_count[price] == price and 1 not in denominations:
return None
# When the number of coins found is multiplied by the minimum
# denomination, and that result is greater than the price, then
# the coins could not be used to create the price.
if coin_count[price] * min(denominations) > price:
return None
return coin_count[price]
Nov. 18, 2019
Comments:
