House Robber

Problem:
https://leetcode.com/problems/house-robber/description/

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed.

The constraint is that adjacent houses cannot both be robbed, because their security systems are connected.

Given an array nums where nums[i] represents the amount of money in the i-th house, return the maximum amount of money you can rob without robbing two adjacent houses.

This is the classic Coin Row dynamic programming problem.

💡 Approach

We define a DP array:

s[i] = maximum money that can be robbed from the first i houses

For each house we have two choices.

1️⃣ Skip the current house

Keep the best result from the previous house.

s[i-1]

2️⃣ Rob the current house

If we rob house i, we must skip house i-1.

nums[i-1] + s[i-2]

So the recurrence is:

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

Why this works

At every house we make the optimal decision between:

• skipping the house
• robbing the house and skipping its neighbor

The DP table stores the best result for all prefixes of the array, allowing us to build the solution incrementally.

Time complexity: O(n)
Space complexity: O(n)

def rob(nums):
    # DP table where s[i] is best we can do with first i houses
    s = [0] * (len(nums) + 1)

    # base case
    s[1] = nums[0]

    for i in range(2, len(s)):
        # choice: rob current house or skip it
        s[i] = max(s[i-2] + nums[i-1], s[i-1])

    return s[-1]


# example test
print(rob([2, 7, 9, 3, 1]))