State

dp[i] = max loot considering first i houses.

Advertisement

Transition

dp[i] = max(
  dp[i-1],              // skip house i
  dp[i-2] + houses[i]   // rob house i
);
Advertisement

Space O(1)

int prev1 = 0, prev2 = 0;
for (int h : houses) {
  int cur = Math.max(prev1, prev2 + h);
  prev2 = prev1; prev1 = cur;
}
return prev1;

Circular variant

Houses in a circle: first + last adjacent. Solve twice — with first, without last; without first, with last. Return max.