House Robber

The input 1,2,3,1 lists the cash in four houses on a street, left to right: $1, 2, 3, 1$ . The output is the largest total you can collect.
The only rule: no two neighbouring houses may both be chosen. So houses 1 and 2, 2 and 3, or 3 and 4 never appear together.
With four houses, the allowed picks of two or more are $\{1,3\}$ , $\{1,4\}$ and $\{2,4\}$ . Three houses are impossible, since any three of four contain a neighbouring pair.
Their totals: $\{1,3\} \to 1 + 3 = 4$ , $\{1,4\} \to 1 + 1 = 2$ , $\{2,4\} \to 2 + 1 = 3$ . A single house gives at most $3$ .
The best is $4$ , from houses 1 and 3. Notice that taking the richest house (house 3) rules out both its neighbours, but house 1 is still free to add on.

Background Knowledge

The "House Robber" problem is a classic example of a dynamic programming problem. Dynamic programming is a method for solving complex problems by breaking them down into simpler subproblems, solving each subproblem only once, and storing the solutions to subproblems to avoid redundant computation. This approach is particularly useful for problems that have overlapping subproblems or optimal substructure, meaning 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 the "House Robber" problem, we need to consider the maximum amount of money that can be robbed from a sequence of houses, with the constraint that no two adjacent houses can be robbed. This problem can be viewed as a sequence of decisions, where at each step, we decide whether to rob the current house or not. The decision at each step depends on the decisions made at previous steps, which is a characteristic of dynamic programming problems.

To solve this problem, we need to understand the concept of state and transition in dynamic programming. The state represents the current situation, and the transition represents the action taken to move from one state to another. In this problem, the state can be represented by the current house and the amount of money robbed so far. The transition can be represented by the decision to rob or not rob the current house.

Algorithm/Approach

The algorithm pattern to solve this type of problem is to use a bottom-up dynamic programming approach. This involves starting from the base case (i.e., the first house) and iteratively building up the solution to the larger problem. We will use a table (e.g., an array) to store the solutions to subproblems, where each entry in the table represents the maximum amount of money that can be robbed up to a certain point.

Step-by-Step Strategy

To implement the solution, follow these steps:

Define the base case: Determine the maximum amount of money that can be robbed from the first house.
Initialize the table: Create a table to store the solutions to subproblems.
Fill the table: Iterate through the sequence of houses, and for each house, calculate the maximum amount of money that can be robbed up to that point.
Calculate the final answer: The final answer will be stored in the last entry of the table.

Common Pitfalls

When implementing the solution, watch out for the following:

Make sure to handle the base case correctly.
Ensure that the table is initialized correctly.
Be careful when calculating the maximum amount of money that can be robbed up to each point, as this will depend on the decisions made at previous steps.

Time & Space Complexity

The expected time complexity for this problem is $O(n)$ , where $n$ is the number of houses, since we need to iterate through the sequence of houses once. The expected space complexity is also $O(n)$ , since we need to store the solutions to subproblems in a table of size $n$ .

Example

Constraints

Learn this in

More from Blind 75

Background Knowledge

Algorithm/Approach

Step-by-Step Strategy

Common Pitfalls

Time & Space Complexity