# House Robber

## House Robber I ([LC.198](https://leetcode.com/problems/house-robber/))

> You plan to rob a neighborhood. The constraint is that you are not allowed to rob adjacent houses. And your objectively is obviously to maximize your earning. Given an array where money\[i] = money stored at house\_i, return the maximum amount of money you can rob.

## Example

```
Input: [3, 8, 1, 2, 5, 6]
Return: 8 + 2 + 6 = 16
```

## Analysis

Maximization/minimization on an array usually can be solved with DP. So does this one.

## Approach

```
1. define optimal subproblems by prefix
    rob(n) = max amount of money at house n
2. solve by prefix, 2 optionas, rob nth house or skip it
    rob(n) = Math.max(rob(n-1), rob(n-2) + money[n]);
3. topo order
    for i from 2 to n
4. init base cases
    rob(0) = 0
    rob(1) = money[0]
5. answer
    return rob(n)
```

## Code

```java
public int rob(int[] money) {
    // edge cases
    if (money == null || money.length == 0) {
        return 0;
    }
    // create memo table
    int[] memo = new int[money.length + 1];
    // init base cases
    memo[0] = 0;
    memo[1] = money[0];
    // topo order
    for (int i = 2; i < memo.length; i++) {
        memo[i] = Math.max(memo[i-1], memo[i-2] + money[i-1]);
    }
    // answer
    return memo[memo.length-1];
}
```

Notice the recurrence only uses `memo[i-1]` and `memo[i-2]`. So we can just use two variables to replace the memo table as long as we update both of them inside the for loop.

## Updated Code

```java
public int rob(int[] money) {
    // edge cases
    if (money == null || money.length == 0) {
        return 0;
    }
    // create memo vars & init base cases
    int last = 0;
    int current = money[0];
    // topo order
    for (int i = 1; i < money.length; i++) {
        int temp = current;
        current = Math.max(current, last + money[i]);
        last = temp;
    }
    // answer
    return current;
}
```

## Time & Space Complexity

Time - O(n)\
Space - O(n) (can be reduced to O(1))

## House Robber II ([LC.213](https://leetcode.com/problems/house-robber-ii/))

> Adding an extra constraint: you can only rob either the first house or the last house. The neighborhood is a circle.

## Approach

```
func rob2(int[] money)
    int earning1 = rob(money[1:n]) // rob from 2nd house to the last one
    int earning2 = rob(money[0:n-1]) // rob from 1st house to the second last one
    return Math.max(earning1, earning2)
end func
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://zedive.gitbook.io/project-l/part-2/dynamic_programming/coordinate-dp/house-robber.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.