House Robber

  # ----------------------------------------
  # 2. House Robber - Classic 1D DP
  #
  # Problem: Rob houses in a line, but can't rob adjacent houses.
  # Find maximum money you can rob.
  #
  # Input: [2, 7, 9, 3, 1]
  # Output: 12 (rob houses 0, 2, 4 → 2 + 9 + 1 = 12)
  #
  # Time Complexity: O(n)
  # Space Complexity: O(1)
  # ----------------------------------------
  def house_robber(nums)
    return 0 if nums.empty?
    return nums[0] if nums.length == 1
    
    prev2, prev1 = 0, nums[0]
    puts "House 0: max = #{prev1}"
    
    (1...nums.length).each do |i|
      current = [prev1, prev2 + nums[i]].max
      puts "House #{i}: max(#{prev1}, #{prev2} + #{nums[i]}) = #{current}"
      prev2, prev1 = prev1, current
    end
    
    puts "Maximum money robbed: #{prev1}"
    prev1