# Dynamic Programming Solution for the House Robber Problem: Complete Guide

> Learn the dynamic programming solution for the House Robber problem. Discover how to maximize loot without robbing adjacent houses using a bottom-up approach and recurrence relation.

- Repository: [Kevin Naughton Jr./interviews](https://github.com/kdn251/interviews)
- Tags: deep-dive
- Published: 2026-03-04

---

**The dynamic programming solution for the House Robber problem utilizes a bottom‑up approach with the recurrence relation `dp[i] = max(dp[i‑2] + nums[i], dp[i‑1])` to compute the maximum loot obtainable without robbing adjacent houses.**

The House Robber problem is a fundamental algorithmic challenge that demonstrates optimal substructure in dynamic programming. As implemented in the **kdn251/interviews** repository, this solution transforms an exponential recursive approach into an efficient linear‑time algorithm. This guide examines the exact source code from [`leetcode/dynamic-programming/HouseRobber.java`](https://github.com/kdn251/interviews/blob/main/leetcode/dynamic-programming/HouseRobber.java) to explain how the DP state tracks maximum profits across a street of houses.

## Understanding the DP State and Recurrence

The solution maintains a **DP array** where `dp[i]` stores the maximum money robable from the first `i + 1` houses. This definition captures the critical insight: the optimal decision at house `i` depends solely on the best results from houses `i‑1` and `i‑2`.

For each house starting at index `2`, the algorithm evaluates two exclusive choices:

- **Rob house `i`**: Add `nums[i]` to the optimal amount from house `i‑2` (`dp[i‑2] + nums[i]`)
- **Skip house `i`**: Retain the optimal amount from house `i‑1` (`dp[i‑1]`)

The recurrence relation implemented in the `rob()` method is:

```

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

```

Base cases handle edge scenarios: an empty list returns `0`, and a single element returns `nums[0]`.

## Java Implementation from kdn251/interviews

The primary implementation resides in [`leetcode/dynamic-programming/HouseRobber.java`](https://github.com/kdn251/interviews/blob/main/leetcode/dynamic-programming/HouseRobber.java). The class initializes the DP array, seeds the first two values, and iteratively applies the recurrence relation.

```java
public class HouseRobber {
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        if (nums.length == 1) return nums[0];
        
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        
        for (int i = 2; i < nums.length; i++) {
            dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
        }
        
        return dp[nums.length - 1];
    }
}

```

You can utilize this implementation as follows:

```java
public class Demo {
    public static void main(String[] args) {
        int[] houses = {2, 7, 9, 3, 1};
        HouseRobber solver = new HouseRobber();
        int maxLoot = solver.rob(houses);
        System.out.println("Maximum amount that can be robbed: " + maxLoot);
        // Output: Maximum amount that can be robbed: 12
    }
}

```

For the input `{2, 7, 9, 3, 1}`, the DP array evolves as `[2, 7, 11, 11, 12]`. The final value **12** represents the optimal strategy of robbing houses at indices 0, 2, and 4.

## Complexity Analysis

The algorithm achieves **O(n)** time complexity, performing a single pass through the input array of length `n`. Space complexity is **O(n)** due to the DP array storage, though the logic only requires the previous two states and can be optimized to **O(1)** auxiliary space.

## Company‑Specific Variations

The kdn251/interviews repository distributes this solution across multiple directories for targeted interview preparation:

- **[`company/linkedin/HouseRobber.java`](https://github.com/kdn251/interviews/blob/main/company/linkedin/HouseRobber.java)**: Identical DP logic packaged for LinkedIn interview contexts
- **[`company/airbnb/HouseRobber.java`](https://github.com/kdn251/interviews/blob/main/company/airbnb/HouseRobber.java)**: Airbnb‑specific version with the same recurrence implementation
- **[`leetcode/dynamic-programming/HouseRobberII.java`](https://github.com/kdn251/interviews/blob/main/leetcode/dynamic-programming/HouseRobberII.java)**: Solves the circular variant where houses are arranged in a ring, requiring two passes of the standard algorithm (excluding the first house in one pass and the last house in the other)

## Summary

- The **dynamic programming solution for the House Robber problem** relies on the recurrence `dp[i] = max(dp[i‑2] + nums[i], dp[i‑1])` to build optimal substructure iteratively.
- The implementation in [`leetcode/dynamic-programming/HouseRobber.java`](https://github.com/kdn251/interviews/blob/main/leetcode/dynamic-programming/HouseRobber.java) executes in **O(n)** time with **O(n)** space complexity.
- Edge cases for empty or single‑house inputs are handled explicitly before entering the main loop.
- The repository provides company‑specific adaptations for LinkedIn and Airbnb, plus the circular variant [`HouseRobberII.java`](https://github.com/kdn251/interviews/blob/main/HouseRobberII.java).

## Frequently Asked Questions

### What is the recurrence relation for the House Robber dynamic programming solution?

The recurrence relation is `dp[i] = max(dp[i‑2] + nums[i], dp[i‑1])`. At each house `i`, you either add the current house's value to the best result from two houses back, or you carry forward the best result from the previous house, whichever yields a higher total.

### Can the House Robber DP solution be optimized to use constant space?

Yes. While the `kdn251/interviews` implementation uses an **O(n)** array for clarity, you can reduce space to **O(1)** by maintaining only two variables to track `dp[i‑1]` and `dp[i‑2]`, since the calculation at each step only depends on these previous two values.

### How does the House Robber II variant differ from the original problem?

According to [`leetcode/dynamic-programming/HouseRobberII.java`](https://github.com/kdn251/interviews/blob/main/leetcode/dynamic-programming/HouseRobberII.java), the circular variant treats the first and last houses as adjacent. The solution executes the standard algorithm twice—once on the range excluding the first house and once excluding the last house—then returns the maximum of the two results.

### Why does the solution return `dp[n‑1]` instead of the maximum value in the DP array?

The DP array is constructed to be monotonically non‑decreasing because `dp[i]` represents the maximum loot possible from houses `0` through `i`. Therefore, the last element `dp[n‑1]` inherently contains the global maximum for all `n` houses, making a separate max search unnecessary.