LeetCode Study Note | Problem 198: House Robber

🏠 Problem Overview

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, but adjacent houses have security systems connected — so robbing two adjacent houses will trigger the alarm.

Task: 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.

⭐ Why This Problem is Great for DP Beginners

House Robber is an excellent entry point into dynamic programming. If you’re still unsure about how DP works, this problem walks you through the 4 fundamental steps of solving DP problems.

1️⃣ Define Subproblems

Let’s define the subproblem as:

• f(k): the maximum amount of money that can be robbed from the first k houses.

A valid DP subproblem must satisfy:

• The full problem can be derived from subproblems.

• A subproblem must be computable from even smaller subproblems (optimal substructure).

Here, both conditions are met.

2️⃣ Write the Recurrence Relation

For each house k, we have two choices:

1. Skip house k: take the result of f(k-1)

2. Rob house k: rob house k-1 (since index is 0-based), then add f(k-2)

f(k) = max(f(k-1), f(k-2) + H[k-1])

Base cases:

f(0) = 0
f(1) = H[0]

3️⃣ Determine DP Array Order

Each f(k) depends on f(k-1) and f(k-2). This forward dependency suggests a left-to-right filling of the DP array.

💻 Code (with DP Array)

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

    int N = nums.length;
    int[] dp = new int[N + 1];

    dp[0] = 0;
    dp[1] = nums[0];

    for (int k = 2; k <= N; k++) {
        dp[k] = Math.max(dp[k - 1], nums[k - 1] + dp[k - 2]);
    }

    return dp[N];
}

4️⃣ Space Optimization

Since each step only relies on the previous two results, we don’t need the whole DP array — just two variables.

⚙️ Optimized Code (O(1) Space)

public int rob(int[] nums) {
    int prev = 0, curr = 0;

    for (int i : nums) {
        int temp = Math.max(curr, prev + i);
        prev = curr;
        curr = temp;
    }

    return curr;
}

📊 Complexity Analysis

✨ Summary

The House Robber problem teaches the core of dynamic programming:

• Define subproblems

• Find recurrence

• Fill bottom-up

• (Optionally) optimize space