memo make change

gistfile1.rb

def make_change(amount)
  mc(amount, 5)
end

def mc(amount, kinds_of_coins)
  return 1 if amount == 0
  return 0 if amount < 0 || kinds_of_coins == 0
  other_coins = mc(amount, kinds_of_coins - 1)
  remove_largest_coin = mc(amount - next_denom(kinds_of_coins), kinds_of_coins)
  other_coins + remove_largest_coin

end

def next_denom(n)
  [1, 5, 10, 25, 50][n-1]
end

def memo_make_change(amount)
  mc = Hash.new do |hash, key|
    am, kinds = key
    if am == 0
      hash[key] = 1
    elsif am < 0 || kinds == 0
      hash[key] = 0
    else
      first = [am, kinds - 1]
      second = [am - next_denom(kinds), kinds]
      hash[key] = hash[first] + hash[second]
    end
  end

  mc[[amount, 5]]
end