In algorithm design, dynamic programming is a powerful tool for solving optimization problems by breaking them down into smaller overlapping subproblems. A classic challenge that perfectly demonstrates this paradigm is LeetCode's House Robber problem.

The problem statement describes a robber planning to rob houses along a street. Each house contains a certain amount of cash. However, neighboring houses have connected security alarms; if the robber breaks into two adjacent houses on the same night, the system alerts the police.

Given an array of integers representing the money in each house, our goal is to find the maximum sum of money we can rob without robbing adjacent houses.

For instance, given the loot values [2, 7, 9, 3, 1], robbing the first, third, and fifth houses yields the optimal total of 2 + 9 + 1 = 12. In this guide, we will walk through the logic of transition states to design an optimized, space-efficient Java solution.

Real-World Analogy: The Gold Coin Stepping Stones

To visualize this problem, imagine walking along a pathway of stepping stones. Each stone has a specific number of gold coins sitting on it. The catch is that stepping on two adjacent stones triggers a loud siren.

As you stand before each stepping stone, you must make a choice:

  • Option 1 (Step on it): You collect the gold on the current stone. Because you cannot step on the immediate predecessor, your total gold is the coin value of the current stone plus the maximum gold accumulated up to two stones ago.
  • Option 2 (Skip it): You skip the current stone. Your total gold is simply the maximum amount of gold you had collected up to the previous stone.
To maximize your loot, you choose the option that yields the larger sum. You repeat this decision at every stone, carrying forward your running total.

Dynamic Programming Strategies

1. The Full State Array Approach (O(N) Time, O(N) Space)

We can allocate a dp array where dp[i] represents the maximum loot we can get from robbing the first i houses. At the i-th house, our recurrence relation is: dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i]). This builds a complete historical ledger of all optimal paths.

2. Space-Optimized Approach (O(N) Time, O(1) Space)

Since calculating the state for house i only requires the values of the last two states (dp[i-1] and dp[i-2]), storing the entire array is redundant. We can keep track of these two states using two variables:

  • prev1: The maximum money robbed up to the previous house.
  • prev2: The maximum money robbed up to two houses ago.
As we iterate through each house, we compute the current maximum, then shift prev2 and prev1 forward. This achieves linear runtime with zero extra space overhead.

Step-by-Step Scenario Walkthrough

Let's trace the space-optimized algorithm with the array nums = [2, 7, 9, 3, 1]:

  • Initialization: Set prev1 = 0, prev2 = 0.
  • House 1 (val = 2): Max loot is Math.max(prev2 + 2, prev1) = Math.max(0 + 2, 0) = 2. Update: prev2 = 0, prev1 = 2.
  • House 2 (val = 7): Max loot is Math.max(prev2 + 7, prev1) = Math.max(0 + 7, 2) = 7. Update: prev2 = 2, prev1 = 7.
  • House 3 (val = 9): Max loot is Math.max(prev2 + 9, prev1) = Math.max(2 + 9, 7) = 11. Update: prev2 = 7, prev1 = 11.
  • House 4 (val = 3): Max loot is Math.max(prev2 + 3, prev1) = Math.max(7 + 3, 11) = 11. Update: prev2 = 11, prev1 = 11.
  • House 5 (val = 1): Max loot is Math.max(prev2 + 1, prev1) = Math.max(11 + 1, 11) = 12. Update: prev2 = 11, prev1 = 12.
The loop terminates, and we return the final value of prev1, which is 12.

Key Code Explanations

Here is why the main logic in the solution is important:

  • int temp = prev1;: Caches the previous house's total loot so it can become the value for "two houses ago" (prev2) in the next step.
  • Math.max(prev2 + num, prev1);: Evaluates the fundamental subproblem choice—should we rob the current house (taking money from two houses ago + current loot) or skip it (taking previous house's total loot)?

Java Implementation Code

Below is the complete, self-contained Java source code that solves this problem. It also includes a main method that traces the execution with console outputs.

package io.practise.dsa;
 
import java.util.Arrays;
 
public class HouseRobber {
 
    // Space-Optimized Dynamic Programming: Time O(N), Space O(1)
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        
        int prev1 = 0; // Represents max loot up to house i-1
        int prev2 = 0; // Represents max loot up to house i-2
        
        for (int num : nums) {
            int temp = prev1;
            prev1 = Math.max(prev2 + num, prev1);
            prev2 = temp;
        }
        
        return prev1;
    }
 
    public static void main(String[] args) {
        HouseRobber solver = new HouseRobber();
        int[] houses = {2, 7, 9, 3, 1};
 
        System.out.println("--- House Robber Demonstration ---");
        System.out.println("Loot values of houses: " + Arrays.toString(houses));
        int maxLoot = solver.rob(houses);
        System.out.println("Maximum possible loot: " + maxLoot); // Expected: 12
    }
}

Conclusion & Complexity Analysis

By identifying that state transitions depend only on the immediate past two values, we reduce the space complexity from O(N) to O(1) constant space, while maintaining a fast linear O(N) runtime complexity. This is the optimal design for resource allocation questions.