Coin Change

coin_change.rb

# https://leetcode.com/problems/coin-change/?envType=problem-list-v2&envId=oizxjoit

def coin_change(coins, amount)
  # The cache remembers how many coins it takes to make a certain amount
  cache = {}

  coin_change_recurser(
    original_amount: amount,
    coins: coins.sort.reverse,
    current_coin_count: 0,
    amount_left: amount,
    cache:
  ) || -1
end

# @return [Integer, nil]
def coin_change_recurser(
  original_amount:,
  coins:,
  current_coin_count:,
  amount_left:,
  cache:
)
  # If the amount left is 0, we've made the correct amount of change
  # so just return current coin count.
  if amount_left == 0
    return current_coin_count
  end

  # We couldn't make the correct change, return nil, meaning no solution
  if amount_left < 0
    return nil
  end

  # If the cache remembers how to make this amount of change,
  # then just use it.  I was worried that the cache may have cached
  # a sub-optimal solution before hand, but I don't we have to worry
  # about this, since the cache is built up from when current_coin_count is 0.
  if cache[amount_left]
    return current_coin_count + cache[amount_left]
  end

  # Update cache before recursion
  amount_made = original_amount - amount_left
  if amount_made > 0
    if cache[amount_made]
      # If we've cached this amount made before, save it only if its better (ie uses fewer coins)
      if cache[amount_made] > current_coin_count
        cache[amount_made] = current_coin_count
      end
    else
      # Cache that we have made this amount before using this amount of coins
      cache[amount_made] = current_coin_count
    end
  end

  results = coins.map do |coin|
    coin_change_recurser(
      original_amount:,
      coins:,
      current_coin_count: current_coin_count + 1,
      amount_left: amount_left - coin,
      cache:
    )
  end

  answer = results.compact.min

  # Return nil if answer doesn't exist
  return if answer.nil?

  # Otherwise, return the answer
  answer
end

puts coin_change([1, 2, 5], 11)
puts coin_change([2], 3)
puts coin_change([1], 0)