House Robber
Problem statement
A row of batch jobs is lined up in time slots, and nums[i] is the value of running the job in slot i. Because of a cooldown rule, you can never run jobs in two adjacent slots. Choose which jobs to run so the total value is as large as possible, and return that total.
The list has at least one slot and all values are non-negative. (LeetCode tells the same story with houses on a street and a robber who can't hit two neighbours.)
Examples
Example 1
Input: nums = [2,9,4,3,8]
Output: 17
Explanation: Run slots 1 and 4 for 9 + 8. Taking every other slot from the start (2 + 4 + 8) gives only 14.
Example 2
Input: nums = [5,1,1,5]
Output: 10
Explanation: Slots 0 and 3. They are not adjacent, and skipping two slots in a row is allowed.
Hints
Approach
Two running values. Walk left to right with skip, the best total up to the previous slot, and prev2, the best total up to the slot before that. For each value x, the new best is max(skip, prev2 + x); then shift both forward. No recursion, no array.
O(n)Space O(1)def rob(nums): prev2, prev1 = 0, 0 # best up to i-2, best up to i-1 for x in nums: prev2, prev1 = prev1, max(prev1, prev2 + x) return prev1 print(rob([2, 9, 4, 3, 8]))print(rob([5, 1, 1, 5]))Follow-up questions
- Return which slots were chosen, not only the total.
- The values sit on a binary tree and you can't pick a parent and its child (House Robber III).
Frequently asked questions
It is the second classic warm-up DP problem, and the "take it or skip it, with a conflict between neighbours" choice appears in real scheduling: maintenance windows that can't be back to back, or picking non-overlapping jobs for the most value. Interviewers mainly want to see the recurrence stated clearly before the code.
Sometimes the best plan skips two slots in a row, as in [5, 1, 1, 5], where alternating gives only 6. The DP considers every valid pattern, not just the two alternating ones.
The first and last slots become adjacent. Run the linear solution twice, once without the first slot and once without the last, and take the larger result (House Robber II).