Introduction to the House Robber Problem
The House Robber problem is one of the most classic dynamic programming challenges you will encounter in coding interviews and algorithm courses. It presents a deceptively simple scenario: a robber moves down a street lined with houses, each containing a certain amount of money. The catch is that adjacent houses are connected to a security system, and robbing two adjacent houses will trigger an alarm. The goal is to determine the maximum amount of money the robber can steal without alerting the police.
While the premise sounds playful, the problem teaches fundamental concepts that extend far beyond interview preparation. It introduces the core ideas of overlapping subproblems, optimal substructure, and state transitions — the building blocks of dynamic programming. Mastering this problem gives you a mental template you can apply to a wide range of optimization challenges, from resource allocation to scheduling and financial planning.
Why the House Robber Problem Matters
Understanding the House Robber problem matters because it sits at the intersection of simplicity and depth. On the surface, the rules are easy to grasp, but the optimal solution requires careful thinking about how decisions at one step influence decisions at later steps. This trade-off between immediate reward and long-term optimality is a recurring theme in software engineering.
In real-world applications, similar patterns appear in many domains. Consider a cloud service that must choose which jobs to run on adjacent time slots without overloading capacity, or an investment algorithm that must avoid holding conflicting positions on consecutive days. The same dynamic programming structure that solves House Robber can be adapted to model these constraints. By learning the problem thoroughly, you sharpen your ability to recognize when a seemingly unrelated task is actually a variation of a known pattern.
Common Variations You Will See
- Linear street: Houses arranged in a single row, the standard version.
- Circular street: The first and last houses are also adjacent, adding a wrap-around constraint.
- Tree arrangement: Houses connected as nodes in a tree, where parent and child cannot both be robbed.
- With cooldowns or extra constraints: Additional rules about how many houses must be skipped between robberies.
This tutorial focuses on the linear version, but the techniques you learn here form the foundation for tackling all the others.
Understanding the Problem Statement
Given an array of non-negative integers representing the amount of money in each house, return the maximum amount of money you can rob without robbing two adjacent houses. For example, given the input [2, 7, 9, 3, 1], the optimal choice is to rob houses at indices 0, 2, and 4, yielding a total of 2 + 9 + 1 = 12.
The key observation is that for every house, you have exactly two choices: rob it or skip it. If you rob the current house, you cannot rob the previous one, so your total becomes the current house's value plus the best total up to two houses back. If you skip it, your total remains the best total up to the previous house. This binary decision at each step is what makes the problem a perfect fit for dynamic programming.
Step 1: The Recursive Approach
The most intuitive way to think about the problem is recursively. Define a function robFrom(i) that returns the maximum amount you can rob starting from house index i. At each house, you either rob it and add nums[i] to robFrom(i + 2), or skip it and take robFrom(i + 1). The answer is the maximum of these two options.
function robRecursive(nums) {
function robFrom(i) {
if (i >= nums.length) return 0;
const robCurrent = nums[i] + robFrom(i + 2);
const skipCurrent = robFrom(i + 1);
return Math.max(robCurrent, skipCurrent);
}
return robFrom(0);
}
console.log(robRecursive([2, 7, 9, 3, 1])); // 12
This solution is correct but inefficient. Without any form of caching, the same subproblems are recomputed many times, leading to an exponential time complexity of O(2^n). For an array of even 40 houses, this becomes impractical. The next step is to eliminate the redundant work.
Step 2: Adding Memoization
Memoization stores the result of each subproblem the first time it is computed, so subsequent calls return instantly. By caching robFrom(i) in a map or array, we reduce the time complexity to O(n) while keeping the recursive structure intact. This is often called top-down dynamic programming.
function robMemo(nums) {
const memo = new Array(nums.length).fill(-1);
function robFrom(i) {
if (i >= nums.length) return 0;
if (memo[i] !== -1) return memo[i];
const robCurrent = nums[i] + robFrom(i + 2);
const skipCurrent = robFrom(i + 1);
memo[i] = Math.max(robCurrent, skipCurrent);
return memo[i];
}
return robFrom(0);
}
console.log(robMemo([2, 7, 9, 3, 1])); // 12
With memoization, each index is computed exactly once, and the recursion depth is bounded by the length of the array. This version is already suitable for most practical inputs, but we can do even better by removing the recursion entirely.
Step 3: Bottom-Up Dynamic Programming
The bottom-up approach builds the solution iteratively, starting from the smallest subproblems and working toward the final answer. Instead of recursing from index 0 downward, we iterate from the end of the array backward, filling a dp array where dp[i] represents the maximum amount robable from house i to the end.
function robDP(nums) {
if (nums.length === 0) return 0;
if (nums.length === 1) return nums[0];
const dp = new Array(nums.length);
dp[nums.length - 1] = nums[nums.length - 1];
dp[nums.length - 2] = Math.max(nums[nums.length - 1], nums[nums.length - 2]);
for (let i = nums.length - 3; i >= 0; i--) {
dp[i] = Math.max(nums[i] + dp[i + 2], dp[i + 1]);
}
return dp[0];
}
console.log(robDP([2, 7, 9, 3, 1])); // 12
This version runs in O(n) time and uses O(n) space. It is easy to reason about and avoids the overhead of recursive function calls. However, notice that each computation of dp[i] only depends on dp[i + 1] and dp[i + 2]. We do not need the entire array.
Step 4: Space Optimization
Since only two future values are needed at any point, we can replace the dp array with two variables. This reduces the space complexity to O(1) while keeping the time complexity at O(n). This is the version most interviewers expect as a final answer.
function rob(nums) {
if (nums.length === 0) return 0;
if (nums.length === 1) return nums[0];
let prev2 = nums[nums.length - 1];
let prev1 = Math.max(nums[nums.length - 1], nums[nums.length - 2]);
for (let i = nums.length - 3; i >= 0; i--) {
const current = Math.max(nums[i] + prev2, prev1);
prev2 = prev1;
prev1 = current;
}
return prev1;
}
console.log(rob([2, 7, 9, 3, 1])); // 12
You can also write this iteratively from left to right, which often feels more natural. The logic is identical: maintain two variables representing the best totals ending at the previous two positions, and update them as you scan forward.
function robForward(nums) {
let prev2 = 0; // best total up to two houses back
let prev1 = 0; // best total up to the previous house
for (const money of nums) {
const current = Math.max(prev1, prev2 + money);
prev2 = prev1;
prev1 = current;
}
return prev1;
}
console.log(robForward([2, 7, 9, 3, 1])); // 12
This forward version is concise and elegant. The variables prev2 and prev1 start at zero, which neatly handles the edge cases of empty or single-element arrays without separate conditionals.
Handling the Circular Variation
In the circular version of the problem, the first and last houses are considered adjacent. This means you cannot rob both. The trick is to split the problem into two linear subproblems: one excluding the first house, and one excluding the last house. The answer is the maximum of the two results.
function robCircular(nums) {
if (nums.length === 0) return 0;
if (nums.length === 1) return nums[0];
function robLinear(houses) {
let prev2 = 0;
let prev1 = 0;
for (const money of houses) {
const current = Math.max(prev1, prev2 + money);
prev2 = prev1;
prev1 = current;
}
return prev1;
}
const robWithoutFirst = robLinear(nums.slice(1));
const robWithoutLast = robLinear(nums.slice(0, nums.length - 1));
return Math.max(robWithoutFirst, robWithoutLast);
}
console.log(robCircular([2, 3, 2])); // 3
console.log(robCircular([1, 2, 3, 1])); // 4
This decomposition works because any valid solution in the circular case must exclude at least one of the two endpoints. By solving both possibilities and taking the maximum, you cover every valid configuration without double-counting the conflict.
Best Practices
- Start with the brute-force recursion: Writing the naive recursive solution first helps you understand the problem structure before optimizing.
- Identify the state transition early: The recurrence
dp[i] = max(nums[i] + dp[i + 2], dp[i + 1])is the heart of the solution. Once you can articulate it, the rest is implementation detail. - Always check edge cases: Empty arrays, single-element arrays, and arrays with two elements often require special handling or serve as useful sanity checks.
- Reduce space when possible: If your dynamic programming solution only references a fixed number of previous states, replace the array with variables to save memory.
- Test with diverse inputs: Include arrays with zeros, increasing sequences, decreasing sequences, and alternating high-low values to verify correctness.
- Document the recurrence: In an interview or code review, clearly state what each variable represents and why the transition is valid. Clarity matters as much as correctness.
Conclusion
The House Robber problem is a compact yet powerful introduction to dynamic programming. By progressing from a naive recursive solution through memoization, bottom-up iteration, and finally space optimization, you build a clear mental model of how dynamic programming transforms exponential problems into linear ones. The patterns you internalize here — defining a state, writing a recurrence, and eliminating redundant computation — transfer directly to more complex challenges like knapsack problems, sequence alignment, and pathfinding. Practice this problem until the recurrence feels instinctive, and you will have a reliable framework for tackling a wide range of optimization tasks in your day-to-day JavaScript development.