House Robber II: Circular Robbery
Imagine a street with houses arranged in a circle, each containing a certain amount of money. You're a master thief, and your goal is to maximize the amount of money you can steal. However, there's a catch: you cannot rob two adjacent houses. Because the houses are in a circle, the first and the last houses are considered adjacent. This challenge will test your ability to handle dynamic programming with circular constraints.
Problem Description
You are given an array of non-negative integers representing the amount of money in each house. The houses are arranged in a circle, meaning the first house and the last house are adjacent. You need to determine the maximum amount of money you can rob without robbing adjacent houses.
Key Requirements:
- You cannot rob two houses that are next to each other in the circle.
- You must consider the circular nature of the houses, meaning
houses[0]andhouses[n-1]are adjacent.
Expected Behavior: The function should return a single non-negative integer representing the maximum amount of money that can be robbed.
Edge Cases:
- An empty list of houses.
- A list with only one house.
- A list with only two houses.
Examples
Example 1:
Input: [2, 3, 2]
Output: 3
Explanation: Rob house 1 (money = 3). The first house and the last house are adjacent, so you cannot rob house 0 and house 2.
Example 2:
Input: [1, 2, 3, 1]
Output: 4
Explanation: Rob house 0 (money = 1) and then rob house 2 (money = 3). Total = 4. You cannot rob house 1 (adjacent to 0) or house 3 (adjacent to 0 in a circle).
Example 3:
Input: [0]
Output: 0
Explanation: With only one house, you can either rob it or not. Robbing it yields 0, not robbing yields 0. Maximum is 0.
Example 4:
Input: [1, 3]
Output: 3
Explanation: You can rob house 1 (money = 3) or house 0 (money = 1). Since they are adjacent in a circle, you can only rob one. Maximum is 3.
Constraints
0 <= houses.length <= 2000 <= houses[i] <= 1000- The solution should aim for an efficient time complexity, ideally
O(n).
Notes
This problem is a variation of the classic House Robber problem. The circular arrangement introduces an additional constraint. Consider how you can break down this circular problem into subproblems that can be solved using dynamic programming. You might need to consider two separate scenarios to handle the circular adjacency.