Introduction

The House Robber problem is one of the most important Dynamic Programming interview questions.

You are given:

nums[i]

where:

nums[i] represents money stored in house i.

Rule:

You cannot rob two adjacent houses.

Goal:

Maximize the amount of money robbed.

Example

nums = [1,2,3,1]
Output = 4

Explanation:

Rob house 1 and house 3
1 + 3 = 4

Constraints

1 <= nums.length <= 100

Key Observation

For every house:

Two choices exist.

Rob Current House

nums[i] + dp[i-2]

Skip Current House

dp[i-1]

Therefore:

dp[i] = max(nums[i] + dp[i-2],dp[i-1])

This becomes the DP recurrence.

Approach 1 : Memoization

Explanation

Use recursion and store answers.

Steps:

  1. Solve recursively.
  2. Store result.
  3. Reuse previous calculations.
  4. Avoid repeated work.

Approach 2 : Tabulation

Explanation

Build DP array from left to right.

Base Cases:

dp[0] = nums[0]dp[1] = max(nums[0],nums[1])

Transition:

dp[i] = max(nums[i] + dp[i-2],dp[i-1])

Dry Run

Input:

nums = [1,2,3,1]

DP Table:

dp[0] = 1dp[1] = 2
dp[2] = max(3 + 1,2) = 4
dp[3] = max(1 + 2,4) = 4

Answer:

4

Approach 3 : Space Optimized DP

Explanation

Only the previous two states are required.

Instead of storing a full DP array:

prev2prev1

Use two variables.

This reduces:

Space Complexity to O(1)

Practice

Complexity Analysis

Memoization

Time Complexity: O(n)
Space Complexity: O(n)

Tabulation

Time Complexity: O(n)Space Complexity: O(n)

Space Optimized DP

Time Complexity: O(n)Space Complexity: O(1)

Why This Problem is Important

This problem teaches:

  • Pick or Not Pick DP
  • Decision Making
  • State Transition
  • Optimization DP
  • Space Optimization

Real-World Applications

Used in:

  • Resource Allocation
  • Budget Optimization
  • Scheduling Problems
  • Investment Planning
  • Decision Systems

Common Beginner Mistakes

  • Robbing adjacent houses
  • Incorrect base cases
  • Wrong recurrence relation
  • Forgetting edge cases
  • Using greedy instead of DP

Interview Tip

Interviewers expect:

Recursion→ Memoization
→ Tabulation
→ Space Optimization

Always explain:

  • Rob Current House
  • Skip Current House
  • Why DP is required

Related Questions

  • House Robber II
  • Fibonacci
  • Climbing Stairs
  • Coin Change
  • Decode Ways

Final Takeaway

House Robber is the classic Pick-or-Skip Dynamic Programming problem.

It teaches:

  • decision-based DP
  • state transitions
  • optimization techniques
  • space optimization

Mastering House Robber makes many medium and hard DP problems much easier to solve.