Change problem solution

dp-change.rb

COINS = [1,3,6,10,15,20,30,50]

@cache = []

def min_change(amount)
  return 0 if amount == 0
  min = 9999999999

  possible_coins = COINS.select { |n| n <= amount }

  possible_coins.each do |e|
    change = @cache.fetch(amount-e) { min_change(amount-e) }
    min    = [change + 1, min].min
  end

  min
end

amount = 29

(0..amount).each do |i|
  @cache[i] = min_change(i)
end

p @cache
puts "Min change for #{amount} is #{@cache[amount]}"