198 House Robber

This problem introduces an interesting way of thinking—imagine yourself as a robber, moving through a street and deciding which houses to rob. The catch? You can’t rob two adjacent houses, so you must always skip at least one.

I found this guide extremely helpful in explaining how to approach dynamic programming problems. It breaks things down step by step, which makes it easier to understand, but I still need time to digest it all.

Understanding the Problem

The logic behind solving this problem boils down to two choices:

• Rob the current house and add the accumulated amount from two houses before.
• Skip the current house and take the total from robbing the previous house.

Since we want to maximize profit, we never skip three houses because that wouldn’t be optimal—there’s always at least one house in between that can be robbed without triggering an alarm.

Dynamic Programming Approach

We use two variables to track the maximum profit:

• prev1: The maximum amount robbed up to the previous house.
• prev2: The maximum amount robbed up to two houses before.

At the end of the loop, prev1 will always store the largest possible amount that can be robbed.

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

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

        return prev1

Breaking Down the Code

In each iteration:

1. We store the previous prev1 in a temporary variable.
2. We calculate the new prev1 by choosing the larger of:
   • Skipping the current house (prev1 remains unchanged).
   • Robbing the current house and adding it to prev2.
3. Update prev2 to the old prev1 value before moving to the next house.

Final Thoughts

Dynamic programming is still a very new topic for me since I never learned it in university, so I definitely need more practice. But after explaining it in my video, I realized that prev1 will always hold the maximum value at the end of the loop.

Until next time!