Data Structures & Algorithms (Dynamic Programming): House Robber

November 1, 2025

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. The only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given an integer array nums representing the amount of money in each house, return the maximum amount of money you can rob tonight without alerting the police.

Example 1:

Input: nums = [2,7,9,3,1]
Output: 12
Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).
Total amount you can rob = 2 + 9 + 1 = 12.

Example 2:

Input: nums = [2,1,1,2]
Output: 4
Explanation: Rob house 1 (money = 2) and rob house 4 (money = 2).
Total amount you can rob = 2 + 2 = 4.

Solve Here: Leetcode 198

Intuition

The problem is naturally recursive in nature. For every house, we can either rob it and move to the house two steps ahead, or skip the current house and move to the next house.

intuition

Approach 1: Include - Exclude Pattern

Use Recursion to iterate over the houses sequentially. At each index, make a decision to either rob the current house (and skip the next one) or skip the current house and move to the next.

Hypotheses

Let F(currentIndex, nums) be the function that returns the maximum amount of money that can be robbed from the houses in the range [currentIndex, nums.length-1].

Recursive Steps

// Step 1: Rob the current house and go explore the remaining houses in the range [currentIndex + 2, nums.length-1]
int include = nums[currentIndex] + F(currentIndex + 2, nums);

// Step 2: Ignore the current house and go explore the remaining houses in the range [currentIndex + 1, nums.length-1]
int exclude = F(currentIndex + 1, nums);

// Step 3: Return the maximum amount that can be robbed
return Math.max(include, exclude);

Base Conditions

If no houses are left to be robbed, the maximum amount one can accumulate is 0.

if (currentIndex >= nums.length) {
    return 0;
}

Visualization

Array
[2, 7, 9, 3, 1]
Nodes explored
0
Paths reached
0
Best so far
0
State
2
0
7
1
9
2
3
3
1
4
F(?)Press Play or Step → to begin the recursion.
0/25
Active callRob (include)Skip (exclude)Base caseOptimal path

Time Complexity

Each function branches into two choices. This creates a binary recursion tree whose depth is proportional to n (the number of houses). Hence, the overall time complexity = O(2^n).

Space Complexity

At each step, the function moves either one step ahead (i + 1) or two steps ahead (i + 2).

The deepest the recursion can go is when we keep taking the i + 1 path, resulting in a maximum depth of n. Since no additional data structure is used, the overall space complexity = O(n) due to call stack.

Key Observation

The problem exhibits overlapping subproblems, where we repeatedly compute the maximum amount of money that can be robbed across the same subset of houses.

overlapping-subproblems

Approach 2: Memoization

Cache the results of each recursive call in an array to ensure that every subproblem is solved only once. Whenever the same subset of houses are encountred again, reuse the stored result instead of recomputing it.

Hypotheses

Let F(currentIndex, nums, dp) be a function that returns the maximum amount of money that can be robbed from the houses in the range [currentIndex, nums.length - 1].

Here, dp is a 1-D array of size n, where dp[i] stores the maximum amount that can be robbed starting from index i. Each cell can be initialized with -1 to indicate that the result for that index has not yet been computed.

int[] dp = new int[n];
Arrays.fill(dp, -1);

Recursive Steps

// Step 1: Rob the current house and go explore the remaining houses in the range [currentIndex + 2, nums.length-1]
int include = nums[currentIndex] + F(currentIndex + 2, nums, dp);

// Step 2: Ignore the current house and go explore the remaining houses in the range [currentIndex + 1, nums.length-1]
int exclude = F(currentIndex + 1, nums, dp);

// Step 3: Return the maximum amount that can be robbed
return dp[currentIndex] = Math.max(include, exclude);

Base Conditions

If no houses are left to be robbed, the maximum amount one can accumulate is 0.

if (currentIndex >= nums.length) {
    return 0;
}

If the current subproblem has been computed before, return the result stored in dp.

if (dp[currentIndex] != -1) {
    return dp[currentIndex];
}

Visualization

Array
[2, 7, 9, 3, 1]
Nodes explored
0
Cache hits
0
Result F(0)
—
nums
2
0
7
1
9
2
3
3
1
4
dp
−1
0
−1
1
−1
2
−1
3
−1
4
F(?)Press Play or Step → to begin. Watch dp[] fill as each subproblem is solved, and see cache hits short-circuit repeated work.
0/11
Active callRob (include)Skip (exclude)Cache hitBase casedp writes: 0

Time Complexity

Since, we only compute each subproblem F(currentIndex, nums, dp) once and the currentIndex only ranges from 0 to n-1, the overall time complexity = O(n).

Space complexity

We are using a 1-D array of size n to store the results of each subproblem.

The maximum depth the call stack can reach is when we keep taking the i + 1 (exclude) path, resulting in a maximum depth of n.

Therefore, the overall space complexity = O(n).

Key Observation

The result of each subproblem dp[currentIndex] is dependent on the results of the dp[currentIndex + 1] and dp[currentIndex + 2] subproblems.

dp-dependency

Approach 3: Tabulation

Iterate through the houses from right to left, and at each index, compute the maximum amount of money that can be robbed from the houses in the range [currentIndex, nums.length - 1] using the formnula: dp[currentIndex] = Math.max(nums[currentIndex] + dp[currentIndex + 2], dp[currentIndex + 1]).

Algorithm

public int rob(int[] nums) {
    int n = nums.length;
    int[] dp = new int[n];

    for(int i = n - 1; i >= 0; i--) {
        int include = i + 2 < n ? nums[i] + dp[i + 2] : nums[i];
        int exclude = i + 1 < n ? dp[i + 1] : 0;
        dp[i] = Math.max(include, exclude);
    }

    return dp[0];
}

Visualization

nums
2
0
7
1
9
2
3
3
1
4
dp← i
−1
0
−1
1
−1
2
−1
3
−1
4

Fill dp[] from right to left. At each index i: dp[i] = max(nums[i] + dp[i+2], dp[i+1])

0/5

Time Complexity

Since, we are iterating through the houses from right to left, the overall time complexity = O(n).

Space Complexity

We are using a 1-D array of size n to store the results of each subproblem. Therefore, the overall space complexity = O(n).

Key Observation

Each subproblem dp[currentIndex] is only dependent on the results of the dp[currentIndex + 1] and dp[currentIndex + 2] subproblems.

Approach 4: Two Variables

Instead of storing the results of all subproblems in an array, we can use two variables to store the results of the last two subproblems.

Algorithm

public int rob(int[] nums) {
    int n = nums.length;
    int result = 0;

    int next = 0;
    int nextToNext = 0;
    for(int i = n - 1; i >= 0; i--) {
        result = Math.max(nums[i] + nextToNext, next);
        nextToNext = next;
        next = result;
    }

    return result;  
}

Visualization

nums
2
0
7
1
9
2
3
3
1
4
variables
nextToNext
0
dp[i+2]
←
next
0
dp[i+1]

Same as tabulation, but only two variables instead of the full array.

next tracks dp[i+1], nextToNext tracks dp[i+2]. Both start at 0.

0/5

Time Complexity

Since, we are iterating through the houses from right to left, the overall time complexity = O(n).

Space Complexity

We are using two variables to store the results of the last two subproblems. Therefore, the overall space complexity = O(1).