Get the minimum number of coins for a given amount of change

min_coins.rb

$memory = {}
$recursive_count = 0

def get_change(coin_amounts, cents_to_change)
  # memoization to make this faster
  return $memory[cents_to_change] if not $memory[cents_to_change].nil?

  # initalize min_coins to a very large number
  min_coins = 999999999999999
  
  # base cases
  return 0 if cents_to_change == 0
  return 999999999 if cents_to_change < 0
  
  coin_amounts.each do |coin|
    $recursive_count += 1
    
    # recursive call
    num_coins = get_change(coin_amounts, cents_to_change - coin) + 1
    
    # keep a running minimum
    if num_coins < min_coins
      min_coins = num_coins
    end
  end

  # one-line way to do loop above
  # min_coins = coin_amounts.map { |denom| get_change(coin_amounts, cents_to_change - denom) }.min + 1
  
  # remember results of past recursive calls for speed benefits
  $memory[cents_to_change] = min_coins

  min_coins
end

# run method with sample input
puts get_change([1,4,5],8) # should return 2

# puts "recursive calls count: #{$recursive_count}"