DSAverse

Initializing Sorting Algorithms...

Sorting

Trees

Graphs

Preparing interactive visualizations...

Cheatsheet Contact

DSAverse

Dynamic Programming

Loading Dynamic Programming...

DP Table Filling

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

subproblems

O(2^n)→O(n)

DSAverse

Making data structures and algorithms accessible through interactive visualizations.

Quick Links

Home
Contact

Categories

Sorting
Searching
Dynamic Programming

More

Basics
Recursion
Heap Structures
Two Pointers & Sliding Window

© 2025 DSAverse. Built withfor better learning.

Back to Dynamic Programming

House Robber Problem

Watch 1D DP decide at each house whether to rob it or skip it, maximizing money while never touching adjacent houses.

Time: O(n)

Space: O(1) optimized

1D DP Array

Decision Making

House Values (comma-separated):

Speed: 1000ms

Fast (300ms)Slow (2000ms)

Step 1 of 0Phase: start

Neighbourhood

2

House 0

7

House 1

9

House 2

3

House 3

1

House 4

DP Array — Max Money Up To Each House

dp[0]

$0

dp[1]

$0

dp[2]

$0

dp[3]

$0

dp[4]

$0

—

—

—

—

—

Current Step

Click Play to begin

Algorithm Details

Time:O(n)

Space (opt):O(1)

Space (reconstruction):O(n)

Type:1D DP Array

Key Concepts

Constraint: no two adjacent houses
Recurrence: dp[i] = max(nums[i]+dp[i-2], dp[i-1])
Base cases: dp[0]=nums[0], dp[1]=max(nums[0],nums[1])
State: dp[i] = max money up to house i

Knowledge Check

Question 1 of 3

What is the key constraint in the House Robber problem?