gistfile1.txt

#https://leetcode.com/problems/house-robber/submissions/

def show(s)
  p s
end

def rob(nums)
  #show "start"
  res1 = go(0,nums)
  res2 = go(1,nums)
  [res1, res2].max
end
@cache={}

def go(start_pos, nums, hh=[], level =0)
  return 0 unless start_pos<nums.size
  show "start_pos #{start_pos}"

  booty = nums[start_pos]
  #hh<<start_pos
  max=0
  2.upto(3) do |offset|
    next_pos = start_pos+offset
    next if next_pos>=nums.size
    res = @cache[next_pos]
    if res.nil?
      res = go(next_pos, nums, hh, level+1)
      @cache[next_pos] = res
    end
    show "lev:#{level} [#{start_pos}]:[#{offset}] booty #{booty}"
    #show "@cache=#{@cache}"
    max = res if res>max
  end

  booty+=max
end

nums = [183,219,57,193,94,233,202,154,65,240,97,234,100,249,186,66,90,238,168,128,177,235,50,81,185,165,217,207,88,80,112,78,135,62,228,247,211]
#nums = [155,44,52,58,250,225,109,118,211,73,137,96,137,89,174,66,134,26,25,205,239,85,146,73,55,6,122,196,128,50,61,230,94,208,46,243,105,81,157,89,205,78,249,203,238,239,217,212,241,242,157,79,133,66,36,165]
#nums=[2,7,9,3,1]

p nums.size
p rob(nums)