House Robber

Easy

💭 Introduction

You’re a professional robber planning to rob houses along a street. Each house has some amount of money stashed, but — there’s a catch:

Adjacent houses have security systems connected. If you rob two directly connected houses, you get caught.

Your goal is to maximize the total money you can rob without triggering the alarm.

🧩 Problem Statement

LeetCode #198 — House Robber

You are given an integer array nums representing the amount of money in each house. You cannot rob two adjacent houses. Return the maximum amount of money you can rob tonight without alerting the police.

🔍 Example 1:

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

Explanation:

Rob house 1 (money = 1) and house 3 (money = 3). Total = 1 + 3 = 4.

🔍 Example 2:

Input: nums = [2,7,9,3,1]
Output: 12

Explanation:

Rob house 1 (2), skip house 2, rob house 3 (9), skip 4, rob house 5 (1). Total = 2 + 9 + 1 = 12.

🧠 Step 1: Brute Force Intuition

Let’s start with the obvious question:

At each house, what choices do you have?

You can either:

1. Rob the current house (but skip the previous one), or

2. Skip the current house and take the result from the previous.

So, for house $i$, the best you can do is:

max_rob(i) = max(
    nums[i] + max_rob(i-2),   # Rob current house
    max_rob(i-1)              # Skip current house
)

This recurrence relation already captures the heart of DP:

1. You’re combining smaller subproblems.

2. Choices depend on previous optimal results.

⚠️ Step 2: The Naive Recursive Approach

Let’s translate that into code first.

def rob(nums):
    def helper(i):
        if i < 0:
            return 0
        return max(nums[i] + helper(i-2), helper(i-1))
    return helper(len(nums) - 1)

This works, but it’s terribly inefficient — because it recomputes the same results again and again.

For example, helper(3) calls helper(1) multiple times.

⏱️ Time Complexity: $O(2^n)$

That’s where Dynamic Programming saves the day.

🚀 Step 3: Top-Down DP (Memoization)

We can store already computed results in a dictionary (memo), avoiding redundant calculations.

class Solution:
    def rob(self, nums: List[int]) -> int:
        memo = {}

        def helper(i):
            if i < 0:
                return 0
            if i in memo:
                return memo[i]

            memo[i] = max(nums[i] + helper(i - 2), helper(i - 1))
            return memo[i]

        return helper(len(nums) - 1)

Now each subproblem (i) is computed once, improving efficiency drastically.

⏱️ Time: $O(n)$

📦 Space: $O(n)$

⚙️ Step 4: Bottom-Up DP (Tabulation)

We can also build a table from the ground up.

Let’s define dp[i] = maximum money that can be robbed up to house $i$.

Transition:

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

Base cases:

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

Now we can fill the table iteratively:

class Solution:
    def rob(self, nums: List[int]) -> int:
        if not nums:
            return 0
        if len(nums) == 1:
            return nums[0]

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

        for i in range(2, len(nums)):
            dp[i] = max(dp[i-1], dp[i-2] + nums[i])

        return dp[-1]

✅ Clean, iterative, and avoids recursion stack overhead.

🧮 Step 5: Space Optimization

Notice that at each step, we only need the previous two states (dp[i-1] and dp[i-2]).

We can reduce the space to $O(1)$ by tracking just two variables.

class Solution:
    def rob(self, nums: List[int]) -> int:
        prev2, prev1 = 0, 0
        for num in nums:
            new_val = max(prev1, prev2 + num)
            prev2 = prev1
            prev1 = new_val
        return prev1

This is the optimal solution — fast, elegant, and space-efficient.

⏱️ Time Complexity: $O(n)$

📦 Space Complexity: $O(1)$