> For the complete documentation index, see [llms.txt](https://private-26.gitbook.io/notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://private-26.gitbook.io/notes/coding/medium/198.-house-robber.md).

# 198. House Robber

## Intitution

In the House Robber problem, the challenge is to maximize the amount of money you can steal without robbing two adjacent houses. This forms a classic **dynamic programming** problem where the decision at each house depends on whether robbing it yields a better total compared to skipping it. The key idea is to make a choice at each step: rob the current house and skip the next, or skip the current house and move to the next one.

## Complexity

| Space Complexity | Time Complexity   |
| ---------------- | ----------------- |
| $$\text{O}(n)$$  | $$\text{O}(2^n)$$ |

## Code

```java
int[] memoizedResults;

public int calculateMaxRobbery(int[] houseMoney, int currentIndex) {
    // Base case: No more houses to rob
    if (currentIndex >= houseMoney.length) return 0;

    // If already computed, return the stored result
    if (memoizedResults[currentIndex] != -1) return memoizedResults[currentIndex];

    // Rob the current house and move to the house after next
    int robThisHouse = houseMoney[currentIndex] + calculateMaxRobbery(houseMoney, currentIndex + 2);

    // Skip the current house and check the next one
    int skipThisHouse = calculateMaxRobbery(houseMoney, currentIndex + 1);

    // Take the maximum of robbing or skipping the current house
    memoizedResults[currentIndex] = Math.max(robThisHouse, skipThisHouse);

    return memoizedResults[currentIndex];
}

public int rob(int[] houseMoney) {
    memoizedResults = new int[houseMoney.length];
    Arrays.fill(memoizedResults, -1); // Initialize memoization array with -1
    return calculateMaxRobbery(houseMoney, 0);
}

```