MediumDynamic Programming

House Robber

Explanation & Solution

Description

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. The only constraint stopping you is that adjacent houses have security systems connected — if two adjacent houses are broken into on the same night, the police will be alerted.

Given an integer array nums representing the amount of money at each house, return the maximum amount of money you can rob tonight without alerting the police.

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

Output: 4

Explanation: Rob house 0 (money = 1) and then rob house 2 (money = 3). Total = 1 + 3 = 4.

Constraints

1 <= nums.length <= 100
0 <= nums[i] <= 400

Approach

Dynamic Programming pattern

1. Define the Subproblem

Let dp[i] be the maximum money you can rob from houses 0 through i
At each house i, you have two choices: rob it or skip it

2. Write the Recurrence

If you rob house i: you cannot rob house i - 1, so the best is dp[i - 2] + nums[i]
If you skip house i: the best remains dp[i - 1]
Therefore dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])

3. Establish Base Cases

dp[-1] = 0 (no houses to rob)
dp[0] = nums[0] (only one house, rob it)
We use prev2 = 0 and prev1 = 0 then iterate, which handles these naturally

4. Optimize Space

Since dp[i] only depends on dp[i - 1] and dp[i - 2], we only need two variables
prev2 tracks the value two steps back, prev1 tracks the value one step back
Update both as we iterate through each house

5. Return the Result

After processing all houses, prev1 holds the maximum amount that can be robbed

Key Insight

This is a classic decision at each step DP: rob or skip, where robbing prevents taking the neighbor

Time

O(n)single pass through the array

Space

O(1)only two variables maintained

Visualization

Input:

Dynamic Programmingnums = [1,2,3,1]

Press play to start DP animation

ComputingDependencyFilledEmpty

5 steps

Solution Code

Climbing Stairs

House Robber II