House Robber

Problem

You are a professional robber planning to rob houses along a street. Adjacent houses have security systems connected — robbing two adjacent houses will alert the police. Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

Examples

The brute-force approach

Try every possible subset of houses. For each subset, check that no two selected houses are adjacent. Track the maximum total among all valid subsets.

max_loot = 0
for each subset of houses:
    if no two houses in subset are adjacent:
        max_loot = max(max_loot, sum of subset)
return max_loot

There are 2^n possible subsets to check, exponential. And many subsets share the same structure. If you know the best outcome through house i−1, you can compute house i's best outcome directly without re-examining all prior houses.

Spotting the pattern

This is a Dynamic Programming problem. The key question to ask yourself:

At each house, which is better: robbing it (plus the best from two houses back), or skipping it (keeping the best from one house back)?

Answering that is where it clicks, and it's exactly what the guided walkthrough below builds with you: the pattern reasoning, a progressive hint ladder that never spoils the answer, a row-by-row dry run, the optimized solution, and an in-browser editor to run your code against real test cases.