💬 Discord
Sign In
NeetCode #660LC-198Medium1-D Dynamic ProgrammingBlind 75NC 150NC 250
← Back to All Problems

#660 · #198 · House Robber(打家劫舍)

📌 Problem Statement & Constraints

You are given a non-negative integer array nums where nums[i] is the money in house i. Return the maximum amount you can rob without robbing two adjacent houses. Constraints: 1 <= nums.length <= 100, 0 <= nums[i] <= 400.

💡 Core Algorithmic Approaches

  1. Let dp[i] be the maximum loot considering houses 0..i.
  2. At house i you either skip it (dp[i - 1]) or rob it (nums[i] + dp[i - 2]), so dp[i] = max(dp[i - 1], nums[i] + dp[i - 2]).
  3. The two choices are exhaustive because robbing i forbids exactly i - 1.
  4. Keep only the last two values to obtain O(1) space.

💻 Benchmark Python3 Implementation

class Solution:
    def rob(self, nums: List[int]) -> int:
        prev2, prev1 = 0, 0            # dp[i-2], dp[i-1]
        for x in nums:
            prev2, prev1 = prev1, max(prev1, prev2 + x)
        return prev1

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): one pass over the houses.
💾 Space Complexity
O(1): two rolling values.

⚠️ Interview Pitfalls & Follow-ups

  • Robbing every other house greedily: for [2, 1, 1, 2] the greedy picks 2 + 1 = 3, but robbing indices 0 and 3 gives 4.
  • Always robbing the current house: you must take the max with the skip option, otherwise [2, 1] would wrongly return 3.
  • Indexing dp[i - 2] for the first house: initialise both rolling values to 0 so i = 0 uses the empty prefix.
  • Sorting the houses: adjacency is positional, so any reordering changes the problem.