198_house_robber.rb

def rob(nums)
  rob_impl(nums, 0)
end

# https://nithinbekal.com/posts/ruby-memoization/
# https://stackoverflow.com/questions/35595047/how-to-generically-memoize-any-function-in-ruby
# We could use a Class instance to hold the memory
def memoize(method_name)
  memory = {}
  original = method(method_name)

  # Needs to rebind the method name because of the recursive calls in the original method
  define_method(method_name) do |*args|
    if memory.include?(args)
      memory[args] 
    else
      memory[args] = original.call(*args)
    end
  end
end

memoize def rob_impl(nums, start_index)
  if start_index >= nums.length - 1
    nums[start_index] || 0
  else
    [
      nums[start_index] + rob_impl(nums, start_index + 2),
      rob_impl(nums, start_index + 1)
    ].max
  end
end