def change(amount, denominations):
    '''Returns the least number of coins required to make the given
    amount using the list of provided denominations.'''
    if amount == 0:
        return 0
    if not denominations:
        return float('infinity')
    if denominations[0] > amount:
        best = change(amount, denominations[1:])
    else:
        useIt = 1 + change(amount - denominations[0], denominations)
        loseIt = change(amount, denominations[1:])
        best = min(useIt, loseIt)
    return best

# change(42, (25, 21, 10, 1))
# 2
# change(1050, (25, 24, 10, 1))
# 42

def change_memo(amount, denominations):
    return change_memoR(amount, denominations, {})

def change_memoR(amount, denominations, memo):
    '''Returns the least number of coins required to make the given
    amount using the list of provided denominations.'''
    
    if amount == 0:
        return 0
    
    if not denominations:
        return float('infinity')
    
    if (amount,denominations) in memo:
        return memo[(amount, denominations)]
    else:
        if denominations[0] > amount:
            best = change_memoR(amount, denominations[1:], memo)
        else:
            useIt = 1 + change_memoR(amount - denominations[0], denominations, memo)
            loseIt = change_memoR(amount, denominations[1:], memo)
            best = min(useIt, loseIt)
        
        memo[(amount, denominations)] = best
        return best