def rob(nums)
  return 0 if nums.empty?
  return nums.max if nums.size <= 2

  dp = Array.new(nums.size-1, 0)
  (0...nums.size).each { |i| dp[i] = [nums[i] + dp[i-2], dp[i-1]].max }
  dp.last
end