178. House Robber
A burglar is working a street of houses laid out in a single row. You receive an integer array nums where nums[i] is the amount of cash stashed in house i. The houses have linked alarms: if two directly neighboring houses are both hit on the same night, the police are called.
Return the largest total amount the burglar can collect in one night without ever robbing two adjacent houses. Skipping any number of houses in a row is always allowed.
This is the classic 'take it or leave it' dynamic program: at every house you either grab its cash and jump past the neighbor, or walk on by.
Example 1:
Input: nums = [1, 2, 3, 1]
Output: 4
Explanation: Hit house 0 (1) and house 2 (3). They are not adjacent, and 1 + 3 = 4 beats every other legal combination.
Example 2:
Input: nums = [2, 7, 9, 3, 1]
Output: 12
Explanation: Hit houses 0, 2, and 4: 2 + 9 + 1 = 12.
Example 3:
Input: nums = [2, 1, 1, 2]
Output: 4
Explanation: The greedy 'every other house' picks fail here — the best plan is houses 0 and 3 for 2 + 2 = 4, skipping two houses in the middle.
Constraints:
- 1 ≤ nums.length ≤ 100
- 0 ≤ nums[i] ≤ 400
Hints:
Define best(i) = the most money obtainable from houses i..end. At house i you have exactly two options: skip it (best(i+1)) or take it (nums[i] + best(i+2)).
That recurrence recomputes the same suffixes exponentially many times — memoize it, or run it bottom-up.
Bottom-up, each answer depends only on the previous two answers. Two rolling variables replace the whole DP array, giving O(1) extra space.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: nums = [1, 2, 3, 1]
Expected output: 4