# LeetCode 198: House Robber — Step-by-Step Visual Trace

**Medium** — Dynamic Programming | Array | Optimization

## The Problem

Given an array of non-negative integers representing the amount of money in each house, determine the maximum amount you can rob without robbing two adjacent houses.

## Approach

Use dynamic programming where dp[i] represents the maximum money that can be robbed up to house i. For each house, choose the maximum between robbing the current house plus the best from two houses back, or keeping the best from the previous house.

**Time:** O(n) · **Space:** O(n)

## Code

```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 - 2] + nums[i], dp[i - 1])

        return dp[-1]
```

## Watch It Run

> **[Open interactive visualization](https://tracelit.dev/app?trace=0198_house-robber)**

> **Try it yourself:** Open [TraceLit](https://tracelit.dev/app?trace=0198_house-robber) and step through every line.

---

*Built with [TraceLit](https://tracelit.dev) — the visual algorithm tracer for LeetCode practice.*