loading

House Robber — Step-by-Step Visualization

mediumLeetCode #198ArrayDynamic Programming

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night. Return the maximum amount of money you can rob tonight without alerting the police.

Algorithm Pattern

Dynamic Programming (Space Optimized)

Key Idea

For each house `i`, we have two choices: 1. Rob it (then we couldn't have robbed house `i-1`). 2. Skip it (then we take the maximum amount we could have robbed up to house `i-1`). The transition is `dp[i] = max(nums[i] + dp[i-2], dp[i-1])`. We only need the previous two results to calculate the current one, so we can use two variables `rob1` and `rob2`.

Step-by-Step Approach

  1. Initialize `rob1 = 0`, `rob2 = 0`.
  2. For each `n` in `nums`:
  3. Calculate `temp = max(n + rob1, rob2)`.
  4. Update `rob1 = rob2`.
  5. Update `rob2 = temp`.
  6. Return `rob2`.

Common Gotchas

  • Think of `rob1` as `dp[i-2]` and `rob2` as `dp[i-1]`.
  • The recurrence ensures no two adjacent houses are robbed.

Related Problems

← All problems