MediumArrayDynamic Programming

House Robber

1 approach, code in every language

A row of houses each hold a certain amount of money, given in an integer array nums. A security system links every pair of directly adjacent houses, so robbing two neighboring houses on the same night triggers an alarm.

Return the largest total amount of money you can steal in one night without ever robbing two adjacent houses.

Example 1

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

Output: 4

Rob house 0 (money = 1) and house 2 (money = 3) for a total of 1 + 3 = 4.

Example 2

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

Output: 12

Rob houses 0, 2, and 4 (2 + 9 + 1 = 12); no two chosen houses are adjacent.

Constraints

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

Two-Variable Rolling DP

Track the best loot up to each house with a decision to skip or rob, using two rolling accumulators.

Loading animation…

Intuition

For each house you face a binary decision: skip it and keep whatever was optimal through the previous house, or rob it and add its money to the best total that ended at least two houses back. Encoding this gives dp[i] = max(dp[i-1], dp[i-2] + nums[i]). Because dp[i] only ever looks one and two positions behind, the full array is unnecessary. We keep prev1 for dp[i-1] and prev2 for dp[i-2] and slide them forward as we scan. Starting both at zero cleanly handles the leading houses. The final value of prev1 is the answer.

Algorithm walkthrough

1Initialize prev2 = 0 (best total two houses back) and prev1 = 0 (best total one house back).
2Scan each house value num from left to right.
3Compute curr = max(prev1, prev2 + num): either skip this house or rob it plus the best from two back.
4Slide the window: set prev2 = prev1, then prev1 = curr.
5Continue until every house has been processed.
6Return prev1, which now holds the maximum loot across the whole street.

Implementation

class Solution:
    def rob(self, nums: List[int]) -> int:
        prev2, prev1 = 0, 0
        for num in nums:
            curr = max(prev1, prev2 + num)
            prev2 = prev1
            prev1 = curr
        return prev1

Time

O(n)

Space

O(1)

One linear scan of the houses; only two running totals are stored regardless of input size.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Dynamic Programming

After the pattern

Now solve one you haven't seen.

Tower Activation Credits is our own problem on the technique behind House Robber: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free