Why it works
- Look at the last house of the first i: either it is left alone, and the best is the one for the first i − 1, or it is robbed, and its neighbour is not, so the best of the first i − 2 plus its money. Nothing else is possible.
- Robbing a house is not always worth it: house 4 brings 4, but taking it rules out the 7 beside it, and 6 + 1 + 4 = 11 loses to 6 + 7 = 13 without it.
- Brute force tries every set of houses, about 2ⁿ of them. The table keeps one best per prefix, and each is built from two earlier cells.
Complexity
Time O(n): one cell per house, each from two earlier cells. Memory O(n) for the table; only the last two cells are ever read, so two variables bring it down to O(1).
nextNow solve it yourself, no hints.
Solve on LeetCode ↗