LeetCode 198 – Python Dynamic Programming Solution (House Robber)

Introduction

The House Robber problem is a classic Dynamic Programming question that frequently appears in coding interviews and online platforms like LeetCode. At first glance, the problem looks simple, but many intuitive approaches fail once edge cases are introduced.

In this article, we’ll explore:

• Why a simple greedy or pattern-based solution does not work
• The correct Dynamic Programming (DP) approach
• A space-optimized solution

---

Problem Statement (LeetCode 198)

You are given an integer array nums where each element represents the amount of money in a house. You cannot rob two adjacent houses. Your task is to return the maximum amount of money you can rob without alerting the police.

---

Initial Intuition (Why It Fails)

A common first thought is to sum all houses at even indices and compare it with the sum of houses at odd indices. While this may work for some cases, it fails because the optimal solution is not restricted to fixed index parity.

For example:

nums = [2, 1, 1, 2]

Even-index sum = 3, Odd-index sum = 3 But the optimal solution is robbing house 0 and house 3 → 2 + 2 = 4.

This shows that we must consider decisions dynamically rather than relying on patterns.

---

Dynamic Programming Approach

Dynamic Programming works by breaking the problem into overlapping subproblems. At each house, we decide:

• Skip the current house → take the money till the previous house
• Rob the current house → add its money to the best result till two houses back

This leads to the recurrence relation:

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

---

DP Implementation (Using Array)

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

        if len(nums) == 2:
            return max(nums[0], nums[1])

        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]

This solution runs in O(n) time and O(n) space.

---

Space Optimized Solution

Since we only need the last two values at any step, we can optimize space to O(1).

class Solution:
    def rob(self, nums: List[int]) -> int:
        prev2 = 0
        prev1 = 0

        for num in nums:
            curr = max(prev1, prev2 + num)
            prev2 = prev1
            prev1 = curr

        return prev1

---

Key Takeaways

• Greedy and fixed-pattern approaches fail for this problem
• Dynamic Programming works because decisions depend on optimal past results
• This problem teaches a reusable DP pattern used in many interview questions

---

Source Code

You can find the complete and clean Python implementation here:

👉 House Robber – Python Solution (GitHub) 👉 House Robber – Python Solution 2 (GitHub)