322_coin_change.rb

# For some reason, only iterative DP passes Leetcode

def coin_change(coins, amount)
  result = coin_change_iterative(coins, amount)
  if result.infinite?
    -1
  else
    result
  end
end

def coin_change_iterative(coins, amount)
  change = Array.new(amount)

  change[0] = 0

  coins.each do |denom|
    change[denom] = 1 if denom < change.length
  end

  0.upto(amount).each do |i|
    change[i] ||= coins.map do |denom|
      inf_dig(change, i - denom) + 1
    end.min
  end

  change[amount]
end

def inf_dig(arr, i)
  if i < 0
    Float::INFINITY
  else
    arr[i]
  end
end

# Normal recursive solution 

# def coin_change(coins, amount)
#   result = coin_change_impl(coins, amount, {})

#   if result.infinite?
#     -1
#   else
#     result
#   end
# end


# def coin_change_impl(coins, amount, mem)
#   mem[coins] ||= {}

#   if mem.dig(coins, amount)
#     mem[coins][amount]
#   else
#     mem[coins][amount] = if amount < 0
#       Float::INFINITY
#     elsif amount == 0
#       0
#     else
#        coins.map do |denom|
#         coin_change_impl(coins, amount - denom, mem) + 1
#       end.min
#     end
#   end
# end


# 
# Class based approach:
# 

# def coin_change(coins, amount)
#   CoinChange.new(coins).call(amount)
# end

# module Memoized
#   def memoize(method_name)
#     original = self.instance_method(method_name)
#     # Needs to redefine the method name because of the recursive calls in the original method
#     self.define_method(method_name) do |*args|
#       # Only use instance variables in instance method definition body
#       @memory ||= {}
#       @memory[method_name] ||= {}

#       if @memory[method_name].include?(args)
#         @memory[method_name][args]
#       else
#         @memory[method_name][args] = original.bind(self).call(*args)
#       end
#     end
#   end
# end


# class CoinChange
#   extend Memoized

#   def initialize(units)
#     @units = units
#   end

#   def call(amount)
#     result = impl(amount)

#     if result.infinite?
#       -1
#     else
#       result
#     end
#   end
  
#   memoize def impl(amount)
#     if amount < 0
#       Float::INFINITY
#     elsif amount == 0
#       0
#     else
#       possible_coins = @units.map do |denom|
#         impl(amount - denom) + 1
#       end.min
#     end
#   end
# end