let rob houses =
  let n = Array.length houses in
  if n = 0 then 0
  else if n = 1 then houses.(0)
  else begin
    let dp = Array.make n 0 in
    dp.(0) <- houses.(0);
    dp.(1) <- if houses.(0) > houses.(1) then houses.(0) else houses.(1);
    for i = 2 to n - 1 do
      let take = dp.(i - 2) + houses.(i) in
      let skip = dp.(i - 1) in
      dp.(i) <- if take > skip then take else skip
    done;
    dp.(n - 1)
  end

;;

rob [| 2; 7; 9; 3; 1; 5; 8; 6 |]
