Skip to content
LEETFLIX

House Robber

MediumArrayDP
Solve on LeetCode

Medium · rob / skip DP. Real solution for this problem — same player as the hand-authored deep-dives.

01

Problem

Read the prompt, flip through the examples, then steal the idea.

LeetCode 198. House Robber. The copyrighted prompt is on LeetCode. This page is a working rob / skip DP for this problem: editable input, Python, Go, and a step-by-step animation.

Constraints

  • —Player inputs are capped so the animation stays readable.
  • —Match LeetCode's own constraints when you submit there.

Examples

Input

nums =
[1, 2, 3, 1]

Output

4

02

Solution

Python and Go. The walkthrough below runs this same code.

Approach 1Optimal▶ Animated

Take or skip, two rolling cells

At house i you either skip it (prev) or take it plus the best from two houses back (prev2 + nums[i]). Adjacent houses cannot both be robbed.

dp[i] = max(dp[i-1], dp[i-2] + nums[i]). Two variables replace the array.

Algorithm

  1. prev2 = 0, prev = 0.
  2. For each house: prev2, prev = prev, max(prev, prev2 + x).
  3. Return prev.
Time
O(n)
Space
O(1)
Solution.py
class Solution:    def rob(self, nums: list[int]) -> int:        prev2 = prev = 0        for x in nums:            prev2, prev = prev, max(prev, prev2 + x)        return prev
Watch this run

03

Interactive walkthrough

Playing “Take or skip, two rolling cells”. Edit the input, hit Run, then scrub.

Approach: Take or skip, two rolling cells

Loading animation…