Dynamic Programming Solution for the House Robber Problem: Complete Guide

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 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. The class initializes the DP array, seeds the first two values, and iteratively applies the recurrence relation.

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:

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: Identical DP logic packaged for LinkedIn interview contexts
• company/airbnb/HouseRobber.java: Airbnb‑specific version with the same recurrence implementation
• 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 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.

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, 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.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}