Module 2 · 1D Dynamic Programming

House Robber

MediumProblem 4 of 30 9 min read ~20 min to solve LeetCode

Dynamic Programming1D DPArrayDecision DP

Asked atAmazonGoogleMicrosoftMetaApple

Problem Statement

You are a robber planning to rob houses along a street. Each house has some money, but adjacent houses have connected security systems. If you rob two adjacent houses, the alarm triggers. Given nums, where nums[i] is the money in house i, return the maximum amount you can rob without robbing adjacent houses.

Input

An integer array nums, where each value is the money available in one house.

Output

An integer: the maximum money that can be robbed without choosing adjacent houses.

Constraints

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

Examples

Example 1

Input:

nums = [1,2,3,1]

Output: 4

Explanation: Rob houses 0 and 2 for a total of 1 + 3 = 4.

Example 2

Input:

nums = [2,7,9,3,1]

Output: 12

Explanation: Rob houses 0, 2, and 4 for a total of 2 + 9 + 1 = 12.

Learning Objectives

Model a choose-or-skip decision as a 1D DP recurrence.
Understand why choosing the current house forces the previous house to be skipped.
Compress the best-prefix table to two rolling values.
Explain the difference between local greed and global optimality.

Intuition

At each house, there are only two meaningful choices. Skip the current house and keep the best answer from the previous index, or rob the current house and add its money to the best answer from two houses back. You cannot combine the current house with the previous house, so those are the only valid options.

A greedy rule like always take the larger neighbour fails because early choices affect later compatibility. DP works because the decision at index i only needs two already-solved prefixes: best through i - 1 and best through i - 2.

Common mistakes

×Choosing the locally larger of each adjacent pair, which can miss better combinations across the whole array.
×Using **dp[i - 1] + nums[i]**, which illegally robs adjacent houses.
×Forgetting that skipping the current house is a valid choice and may be optimal.
×Writing special cases for many array lengths instead of using neutral base values of **0**.

State Definition

Let dp[i] be the maximum money that can be robbed from houses 0 through i, inclusive, without robbing adjacent houses. The answer is dp[n - 1].

State Transition

For house i, either skip it or rob it:

Skip house i: keep dp[i - 1].
Rob house i: take nums[i] + dp[i - 2].

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

Use base values dp[-1] = 0 and dp[-2] = 0 conceptually, which lets the rolling implementation handle the first houses cleanly.

Solutions

Solution: Bottom-up choose-or-skip with rolling values

Track the best answer up to the previous house and the best answer up to two houses back. For each current house, compare skipping it with robbing it.

Step-by-step

Initialise twoHousesBack and oneHouseBack to 0, representing empty prefixes.
For each house value, compute robCurrent = twoHousesBack + value and skipCurrent = oneHouseBack.
The best answer through this house is max(robCurrent, skipCurrent).
Shift the rolling values so the current best becomes the previous best for the next iteration.

Time

O(n)

Space

O(1)

Each house is considered once with two stored prefix answers.

Java implementation

Loading…

Dry Run

Sample input

nums = [2,7,9,3,1]. Start with empty-prefix values twoHousesBack = 0 and oneHouseBack = 0.

index	nums[index]	rob current	skip current	best up to index
0	2	2	0	2
1	7	7	2	7
2	9	11	7	11
3	3	10	11	11
4	1	12	11	12

The best final prefix value is 12, achieved by robbing houses 0, 2, and 4.

Complexity Analysis

The optimal recurrence is linear and constant-space because each decision needs only the two previous prefix answers.

Bottom-up choose-or-skip with rolling values