Learn
Practice
Interview
Resources
Newsletter
F
Toggle theme
0
F
0
Toggle menu
Animations
← Back to All Animations
House Robber III
Bookmark
Naive Recursion
Memoization
Tree DP
Input
Example 1
Example 2
Skewed Tree
Custom
tree
=
[3, 2, 3, null, 3, null, 1]
3
2
3
3
1
each pill = best $ from this house down
max
$?
rob a house → must skip its children
3
2
3
3
1
each pill = best $ from this house down
max
$?
rob a house → must skip its children
3
2
3
3
1
each pill = best $ from this house down
max
$?
left child
is missing, nothing to reach past
3
2
3
3
1
$
3
each pill = best $ from this house down
max
$?
right child
: reach past it to its two grandchildren
0,0
3
2
3
3
1
$
3
each pill = best $ from this house down
max
$?
null child returns
[0, 0]
3
2
3
3
1
$
3
$
1
each pill = best $ from this house down
max
$?
right child
: reach past it to its two grandchildren
3
2
3
3
1
$
1
each pill = best $ from this house down
max
$?
left child
is missing, nothing to reach past
3
2
3
3
1
$
3
$
3
$
1
each pill = best $ from this house down
max
$?
house
2
→ max($
3
, $
3
) = $
3
3
2
3
3
1
$
3
$
3
$
1
each pill = best $ from this house down
max
$?
right grandchildren give $
0
robCurrent = $
3
0,0
3
2
3
3
1
$
3
$
3
each pill = best $ from this house down
max
$?
null child returns
[0, 0]
3
2
3
3
1
$
7
$
3
$
3
$
3
$
1
each pill = best $ from this house down
max
$7
most money the thief can take = $7
algo
master
.
io
Step:
Start House Robber III, naive recursion
0 / 63
Input
Example 1
Example 2
Skewed Tree
Custom
tree
=
[3, 2, 3, null, 3, null, 1]
0 / 63
algo
master
.
io
Step:
Start House Robber III, naive recursion
