House Robber

Maximize loot without robbing adjacent houses using dynamic programming.

dynamic-programming arrays optimization bottom-up

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, given as a list `nums` (length n). The only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and will automatically contact the police if two adjacent houses were broken into on the same night.

Write a function `rob(nums)` that returns the maximum amount of money you can rob tonight without alerting the police.

**Function signature:** `def rob(nums: List[int]) -> int:`

You may assume `List` is already imported from `typing`.

**Examples:**
1. `rob([1, 2, 3, 1])` → `4` (rob house 1 and house 3)
2. `rob([2, 7, 9, 3, 1])` → `12` (rob house 1, house 3, and house 5)
3. `rob([])` → `0`
4. `rob([5])` → `5`

Implement an efficient solution. A dynamic programming approach (either top-down or bottom-up) is expected. The function must handle empty lists and single-element lists.

Constraints

- `0 <= len(nums) <= 1000`
- `0 <= nums[i] <= 10^4`
- Time complexity: O(n)
- Space complexity: O(1) if using optimized DP, O(n) acceptable for clarity.

Example

>>> rob([1, 2, 3, 1])
4
>>> rob([2, 7, 9, 3, 1])
12
>>> rob([])
0
>>> rob([5])
5

10 points ~15 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Think about what choices you have at each house: rob it (and then skip the previous) or skip it.

Define `dp[i]` as the maximum loot from the first `i` houses.

Try to reduce space complexity to O(1) by only keeping track of the last two values.

Consider base cases for empty list and single house.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.