Learn
Practice
Interview
Resources
Newsletter
F
Toggle theme
0
F
0
Toggle menu
Animations
← Back to All Animations
House Robber
Bookmark
Input
Example 1
Example 2
Example 3
Adjacent pattern
Single house
Two houses
Custom
nums
=
[2, 7, 9, 3, 1]
2
?
0
7
?
1
9
?
2
3
?
3
1
?
4
dp
dp[i] = max(dp[i-1], dp[i-2] + nums[i])
2
?
0
7
?
1
9
?
2
3
?
3
1
?
4
dp
dp[i] = max(dp[i-1], dp[i-2] + nums[i])
2
2
0
7
?
1
9
?
2
3
?
3
1
?
4
dp
dp[0]
= nums[0] =
2
rob the only house so far
2
2
0
7
7
1
9
?
2
3
?
3
1
?
4
dp
dp[1]
= max(
2
,
7
) =
7
skip
+9
2
2
0
7
7
1
9
?
2
3
?
3
1
?
4
dp
i
dp[2]
= max(
7
,
2 + 9
) = max(
7
,
11
) =
?
skip
+9
2
2
0
7
7
1
9
11
2
3
?
3
1
?
4
dp
i
dp[2]
= max(
7
,
2 + 9
) = max(
7
,
11
) =
11
skip
+3
2
2
0
7
7
1
9
11
2
3
?
3
1
?
4
dp
i
dp[3]
= max(
11
,
7 + 3
) = max(
11
,
10
) =
?
skip
+3
2
2
0
7
7
1
9
11
2
3
11
3
1
?
4
dp
i
dp[3]
= max(
11
,
7 + 3
) = max(
11
,
10
) =
11
skip
+1
2
2
0
7
7
1
9
11
2
3
11
3
1
?
4
dp
i
dp[4]
= max(
11
,
11 + 1
) = max(
11
,
12
) =
?
skip
+1
2
2
0
7
7
1
9
11
2
3
11
3
1
12
4
dp
i
dp[4]
= max(
11
,
11 + 1
) = max(
11
,
12
) =
12
2
+2
2
0
7
7
1
9
+9
11
2
3
11
3
1
+1
12
4
dp
Max loot =
12
algo
master
.
io
Step:
Start: rob houses for maximum loot without hitting two adjacent ones
0 / 9
Input
Example 1
Example 2
Example 3
Adjacent pattern
Single house
Two houses
Custom
nums
=
[2, 7, 9, 3, 1]
0 / 9
algo
master
.
io
Step:
Start: rob houses for maximum loot without hitting two adjacent ones
