Blind 75Medium

House Robber — Linear DP with Two Choices

At each house decide whether to rob it by comparing robbing plus skipping previous versus skipping now.

Dynamic Programming

Problem Statement

Given non-negative integers representing the amount of money in each house, compute the maximum amount you can rob without alerting the police (no two adjacent houses).

Why This Problem Matters

Introduces DP on linear structures with exclusion constraints.
Prepares you for tree and circular variants of the same pattern.
Clarifies how to maintain two rolling states for include/exclude decisions.

Thought Process

Define dp[i]

dp[i] = max money from first i houses. Transition: dp[i] = max(dp[i-1], dp[i-2] + nums[i-1]).

Space optimise to two variables

Only dp[i-1] and dp[i-2] needed at each step.

Handle small inputs

Return nums[0] when there is a single house.

Step-by-Step Reasoning

If nums length is 1 return nums[0].
Initialise prev2 = nums[0], prev1 = Math.max(nums[0], nums[1]).
For each subsequent house, compute current = Math.max(prev1, prev2 + nums[i]).
Return prev1 after iteration completes.

Dry Run

nums = [1,2,3,1]

dp sequence [1,2,4,4]; answer 4 from robbing houses 1 and 3.

nums = [2,7,9,3,1]

dp sequence [2,7,11,11,12]; answer 12.

Complexity Analysis

Time

O(n)

Space

O(1)

Why

Single pass with constant tracking variables.

Annotated Solution

JAVA

public class HouseRobber {
  public int rob(int[] nums) {
    if (nums.length == 1) {
      return nums[0];
    }

    int prev2 = nums[0];
    int prev1 = Math.max(nums[0], nums[1]);

    for (int i = 2; i < nums.length; i += 1) {
      int current = Math.max(prev1, prev2 + nums[i]);
      prev2 = prev1;
      prev1 = current;
    }

    return prev1;
  }
}

At each step the algorithm chooses between robbing the current house plus dp[i-2] or skipping it and keeping dp[i-1].

Common Pitfalls

Forget to update both prev variables after each iteration results in incorrect sums.
Using dp array but off-by-one indexing by referencing nums[i] incorrectly.
Returning prev2 instead of prev1 loses the latest computation.

Follow-Up Questions

How does the solution change for houses arranged in a circle?
Can you extend the logic to binary trees (House Robber III)?

Key Takeaways

DP with exclusion rules often boils down to a two-state recurrence.

Space optimisation is as simple as rolling two variables.

Always discuss variations such as circular arrangements.