House Robber II

mediumFREEDynamic ProgrammingBlind 75

Same as House Robber: each element of nums is the money in one house, and you cannot rob two adjacent houses. This time the houses are arranged in a circle, so the first and last houses are also adjacent. Implement rob_circular(nums) to return the maximum amount you can rob.

Example

Input

2,3,2

Output

Reasoning

nums lists the money in each house, in order around a circle: house 0 holds $2$ , house 1 holds $3$ , house 2 holds $2$ .
The usual rule applies: no two neighbouring houses may both be robbed. Because the street is a circle, house 2 also neighbours house 0, so with 3 houses every pair is adjacent.
That leaves only single-house choices: $\{0\} \to 2$ , $\{1\} \to 3$ , $\{2\} \to 2$ . Taking both ends would give $2 + 2 = 4$ , which would win on a straight street but is forbidden here.
The best total is $\max(2, 3, 2) = 3$ , so the output is 3.
Notice that the circle only changes the answer when the best straight-line plan uses both the first and the last house. For houses holding $1, 2, 3, 1$ , houses 0 and 2 are not neighbours, so $1 + 3 = 4$ is still allowed.

Constraints

1 <= len(nums) <= 100
0 <= nums[i] <= 1000

Learn this in

Dynamic Programming BasicsDSA Study Plan

More from Blind 75

Alien Dictionaryhard Clone Graphmedium Combination Summedium Word Search IIhard Merge K Sorted Listshard

Concept primer

Background Knowledge

The House Robber II problem is a variation of the classic House Robber problem, which is a fundamental problem in Dynamic Programming. In the House Robber problem, you are given a list of houses, each with a certain amount of money, and you need to find the maximum amount of money you can rob without robbing two adjacent houses. The key concept here is optimal substructure, which means that the problem can be broken down into smaller subproblems, and the optimal solution to the larger problem can be constructed from the optimal solutions of the subproblems.

In the context of Dynamic Programming, the House Robber II problem introduces an additional complexity: the houses are arranged in a circle, which means that the first and last houses are adjacent. This creates a circular dependency, which requires a different approach than the standard House Robber problem. To solve this problem, you need to understand how to modify the recurrence relation to account for the circular dependency.

The Dynamic Programming approach is particularly well-suited for this problem because it allows you to avoid redundant computation and store intermediate results. By using a bottom-up or top-down approach, you can efficiently compute the maximum amount of money that can be robbed. The key is to identify the state and transition functions that define the problem, and then use these functions to compute the optimal solution.

Algorithm/Approach

The general approach to solve this type of problem is to use Dynamic Programming with a modified recurrence relation that accounts for the circular dependency. The algorithm pattern involves:

Defining the state and transition functions that describe the problem
Initializing a table or array to store the intermediate results
Filling in the table using a bottom-up or top-down approach
Computing the maximum or minimum value based on the filled table

Step-by-Step Strategy

To implement the solution, follow these steps:

Define the state function that describes the maximum amount of money that can be robbed up to a given house.
Modify the recurrence relation to account for the circular dependency between the first and last houses.
Initialize a table or array to store the intermediate results.
Fill in the table using a bottom-up approach, starting from the first house and moving clockwise.
Compute the maximum value based on the filled table, considering the two cases where the first house is robbed and where the first house is not robbed.

Common Pitfalls

When implementing the solution, watch out for:

Forgetting to account for the circular dependency between the first and last houses
Using an incorrect recurrence relation that does not consider the circular dependency
Not initializing the table or array correctly
Not considering the two cases where the first house is robbed and where the first house is not robbed

Time & Space Complexity

The expected time complexity is $O(n)$ , where $n$ is the number of houses, and the expected space complexity is $O(n)$ , where $n$ is the number of houses. The time complexity is linear because we only need to fill in the table once, and the space complexity is linear because we need to store the intermediate results in a table of size $n$ .

solution.py

Python 3.13

Test results