House Robber II
Medium · Dynamic Programming · Array · Dynamic Programming
Problem
The houses on this street stand in a circle: house 0 and house n - 1 are neighbors. Each house holds nums[i] in cash, and robbing two neighboring houses on the same night sets off the alarm. Return the most you can take.
Everything else is the original House Robber. The circle adds exactly one rule: the first and the last house cannot both be robbed. A single house has no neighbor, so you simply take it.
[2,3,2] shows the difference. On a straight street you would take both 2s for 4; on the circle they touch, so the best is the 3 alone.
Examples
Input: nums = [2,3,2] Output: 3
Houses 0 and 2 both hold 2, but they are neighbors on the circle. The 3 alone is the best plan.
Input: nums = [1,2,3,1] Output: 4
Rob house 0 (1) and house 2 (3).
Input: nums = [1,2,3] Output: 3
With three houses on a circle, every pair touches, so only one house can be taken: the 3.
Constraints
- 1 <= len(nums) <= 100
- 0 <= nums[i] <= 1000
Approaches
- Memoized recursion, remembering house 0 — time O(n), space O(n)
Follow-up
What if the houses formed a binary tree instead of a circle, so a house's neighbors are its parent and its children (LeetCode 337)? Which part of the take-or-skip idea carries over?
Related problems
Start free on Cariara · Coding problems · System design studio
