House Robber

Asked byAmazonAppleGoogleCiscoMicrosoftAdobe

Problem

You are a robber planning to rob houses arranged in a line, where each house holds a given amount of money. You cannot rob two adjacent houses (doing so triggers an alarm). Return the maximum amount of money you can rob.

Examples

Example 1

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

Output:4

Rob house 1 and house 3 (1 + 3 = 4).

Example 2

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

Output:12

Rob houses 1, 3 and 5 (2 + 9 + 1 = 12).

Constraints

1 <= nums.length <= 100

Solve it in the editor. Sign in free to run your Python or JavaScript against test cases, get a verdict, and track your attempts.

Solve on FeatCode →

How to approach it: the 1-D Dynamic Programming pattern

Break a problem into overlapping subproblems along a single dimension — like "the answer up to index i" — solve each one once, and reuse the result instead of recomputing it.

Look for this pattern when

A greedy or purely recursive approach recomputes the same subproblem repeatedly.
The problem asks for a count, a minimum/maximum, or a yes/no reachability over a sequence, where the answer at position `i` depends on answers at earlier positions.

Read the full 1-D Dynamic Programming guide →

Video walkthroughs

Original problem on LeetCode ↗