House Robber

MediumDynamic ProgrammingArray
Category: 1-D Dynamic Programming
Companies that ask this question:
AmazonGoogleFacebookMicrosoftLinkedIn

Approach

House Robber

Problem Statement

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses at this place are arranged in a line, which means that adjacent houses have security systems connected.

If two adjacent houses are broken into on the same night, the police will be automatically alerted.

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.

Examples

Example 1:

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

Example 2:

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.

Constraints

  • 1 ≤ nums.length ≤ 100
  • 0 ≤ nums[i] ≤ 400

Approach

Key Insight

At each house, you have two choices:

  1. Rob this house - Add current money + max from two houses back (can't rob adjacent)
  2. Skip this house - Keep max from previous house

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

Solution 1: Dynamic Programming (Bottom-Up)

Build the solution from the ground up.

Algorithm:

  1. Base cases:
    • dp[0] = nums[0] (rob first house)
    • dp[1] = max(nums[0], nums[1]) (rob better of first two)
  2. For each house from 2 to n:
    • dp[i] = max(dp[i-1], dp[i-2] + nums[i])
  3. Return dp[n-1]

Solution 2: Space-Optimized DP

We only need the last two values!

Algorithm:

  1. Keep only two variables: prev2 and prev1
  2. For each house:
    • current = max(prev1, prev2 + nums[i])
    • Shift: prev2 = prev1, prev1 = current
  3. Return prev1

Solution 3: Recursion with Memoization (Top-Down)

Recursively solve with caching.

Algorithm:

  1. Base cases: if i < 0, return 0
  2. Use memoization to avoid recalculating
  3. Return max(rob(i-1), rob(i-2) + nums[i])

Complexity Analysis

DP Solution:

  • Time Complexity: O(n) - single pass through array
  • Space Complexity: O(n) - DP array (or O(1) if optimized)

Recursive with Memo:

  • Time Complexity: O(n) - each subproblem solved once
  • Space Complexity: O(n) - memoization cache + recursion stack

Pure Recursion (Not recommended):

  • Time Complexity: O(2^n) - exponential without memoization
  • Space Complexity: O(n) - recursion stack

Pattern Recognition

This problem demonstrates:

  • Dynamic Programming with decision making
  • Max/min optimization pattern
  • Non-adjacent selection constraint
  • Space optimization from O(n) to O(1)
  • Foundation for House Robber II (circular) variant

Solution

java
1import java.util.*;
2
3class Solution {
4    // Solution 1: Dynamic Programming (Bottom-Up)
5    public int rob(int[] nums) {
6        int n = nums.length;
7
8        // Handle edge cases
9        if (n == 0) return 0;
10        if (n == 1) return nums[0];
11
12        // Create DP array
13        int[] dp = new int[n];
14        dp[0] = nums[0];
15        dp[1] = Math.max(nums[0], nums[1]);
16
17        // Fill DP table
18        for (int i = 2; i < n; i++) {
19            // Either rob current house + i-2, or skip current (take i-1)
20            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
21        }
22
23        return dp[n - 1];
24    }
25
26    // Solution 2: Space-Optimized DP (O(1) space)
27    public int robOptimized(int[] nums) {
28        int n = nums.length;
29
30        if (n == 0) return 0;
31        if (n == 1) return nums[0];
32
33        // Only keep track of last two values
34        int prev2 = nums[0];  // dp[i-2]
35        int prev1 = Math.max(nums[0], nums[1]);  // dp[i-1]
36
37        for (int i = 2; i < n; i++) {
38            int current = Math.max(prev1, prev2 + nums[i]);
39            prev2 = prev1;
40            prev1 = current;
41        }
42
43        return prev1;
44    }
45
46    // Solution 3: Recursion with Memoization (Top-Down)
47    private Map<Integer, Integer> memo = new HashMap<>();
48
49    public int robMemo(int[] nums) {
50        return robFrom(nums, nums.length - 1);
51    }
52
53    private int robFrom(int[] nums, int i) {
54        // Base cases
55        if (i < 0) return 0;
56
57        // Check memo
58        if (memo.containsKey(i)) {
59            return memo.get(i);
60        }
61
62        // Recursive case: rob current or skip
63        int result = Math.max(robFrom(nums, i - 1), robFrom(nums, i - 2) + nums[i]);
64        memo.put(i, result);
65
66        return result;
67    }
68}
69
Loading visualizer...