# LeetCode 198: House Robber

## Problem Restatement

We are given an integer array `nums`.

Each element represents the amount of money inside one house.

A robber wants to steal as much money as possible, but there is one restriction:

```text
Two adjacent houses cannot both be robbed.
```

If two adjacent houses are robbed on the same night, the alarm system activates.

We need to return the maximum amount of money that can be robbed without triggering the alarm. The official problem asks for the maximum amount of money that can be robbed without robbing adjacent houses.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Integer array `nums` |
| Output | Maximum possible robbery amount |
| Restriction | Cannot rob adjacent houses |
| Goal | Maximize total money |

Example function shape:

```python
def rob(nums: list[int]) -> int:
    ...
```

## Examples

Example 1:

```python
nums = [1, 2, 3, 1]
```

Possible choices:

| Houses robbed | Total |
|---|---:|
| `1 + 3` | `4` |
| `2 + 1` | `3` |
| `1 + 3 + 1` | invalid |

The best valid choice is:

```text
1 + 3 = 4
```

Answer:

```python
4
```

Example 2:

```python
nums = [2, 7, 9, 3, 1]
```

One good plan:

```text
2 + 9 + 1 = 12
```

Answer:

```python
12
```

## First Thought: Try Every Combination

For every house, we have two choices:

| Choice | Meaning |
|---|---|
| Rob it | Skip the next house |
| Skip it | Move to the next house |

This creates many possible combinations.

For example:

```python
[2, 7, 9, 3]
```

We might choose:

```text
2 + 9
7 + 3
2 + 3
9
...
```

The number of possibilities grows exponentially.

We need a way to reuse previous results.

## Key Insight

At each house, there are only two meaningful possibilities:

| Option | Value |
|---|---|
| Skip current house | Best answer up to previous house |
| Rob current house | Current money + best answer two houses back |

Suppose we are at house `i`.

If we rob house `i`, then house `i - 1` cannot be robbed.

So the total becomes:

```text
nums[i] + best(i - 2)
```

If we skip house `i`, then the total becomes:

```text
best(i - 1)
```

So the recurrence is:

$$
dp[i]=\max(dp[i-1],\ dp[i-2]+nums[i])
$$

This is the core dynamic programming relation.

## Algorithm

1. If there are no houses, return `0`.
2. If there is one house, return its value.
3. Use dynamic programming.
4. For each house:
   - Either skip it.
   - Or rob it and add the best answer from two houses earlier.
5. Return the final maximum value.

## Building the DP Table

Let:

```text
dp[i]
```

mean:

```text
Maximum money we can rob from houses 0..i
```

Base cases:

```python
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])
```

Then for every later house:

```python
dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])
```

## Correctness

For each house `i`, every valid robbery plan falls into one of two categories:

| Category | Meaning |
|---|---|
| House `i` is skipped | Best value is `dp[i - 1]` |
| House `i` is robbed | House `i - 1` must be skipped, so value is `dp[i - 2] + nums[i]` |

No valid plan exists outside these two cases.

The recurrence chooses the better of them.

So `dp[i]` correctly stores the maximum robbery amount for houses `0..i`.

By induction, every DP state is correct, so the final result `dp[n - 1]` is also correct.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | We process each house once |
| Space | `O(n)` | The DP array stores one value per house |

Here, `n` is the number of houses.

## Implementation

```python
class Solution:
    def rob(self, nums: list[int]) -> int:
        n = len(nums)

        if n == 0:
            return 0

        if n == 1:
            return nums[0]

        dp = [0] * n

        dp[0] = nums[0]
        dp[1] = max(nums[0], nums[1])

        for i in range(2, n):
            dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])

        return dp[-1]
```

## Code Explanation

This handles the empty array case:

```python
if n == 0:
    return 0
```

This handles a single house:

```python
if n == 1:
    return nums[0]
```

We create the DP array:

```python
dp = [0] * n
```

This initializes the first house result:

```python
dp[0] = nums[0]
```

For two houses, we choose the larger value:

```python
dp[1] = max(nums[0], nums[1])
```

Then we fill the remaining states:

```python
for i in range(2, n):
    dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])
```

Finally:

```python
return dp[-1]
```

returns the best possible robbery amount.

## Space Optimization

Notice that:

```text
dp[i]
```

depends only on:

```text
dp[i - 1]
dp[i - 2]
```

So we do not need the full array.

We can keep only two variables.

## Optimized Implementation

```python
class Solution:
    def rob(self, nums: list[int]) -> int:
        prev2 = 0
        prev1 = 0

        for money in nums:
            current = max(prev1, prev2 + money)

            prev2 = prev1
            prev1 = current

        return prev1
```

Here:

| Variable | Meaning |
|---|---|
| `prev1` | Best answer up to previous house |
| `prev2` | Best answer up to two houses earlier |

This reduces space complexity to `O(1)`.

## Testing

```python
def run_tests():
    s = Solution()

    assert s.rob([1, 2, 3, 1]) == 4
    assert s.rob([2, 7, 9, 3, 1]) == 12
    assert s.rob([1]) == 1
    assert s.rob([2, 1, 1, 2]) == 4
    assert s.rob([0]) == 0
    assert s.rob([5, 1, 1, 5]) == 10

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `[1,2,3,1]` | Main example |
| `[2,7,9,3,1]` | Multiple optimal transitions |
| `[1]` | Single house |
| `[2,1,1,2]` | Forces skipping adjacent houses |
| `[0]` | Zero-value house |
| `[5,1,1,5]` | Best choice uses first and last houses |