Skip to content

Instantly share code, notes, and snippets.

@matugm
Created June 8, 2015 18:02
Show Gist options
  • Save matugm/4ad3d3190eb32a918af7 to your computer and use it in GitHub Desktop.
Save matugm/4ad3d3190eb32a918af7 to your computer and use it in GitHub Desktop.
Change problem solution
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]}"
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment