Learn
Practice
Interview
Resources
Newsletter
F
Toggle theme
0
F
0
Toggle menu
Animations
← Back to All Animations
Paint House
Bookmark
Recursion
2D DP
Space Optimized
Input
Example 1
Single house
4 houses
Custom
costs
=
[[17,2,17],[16,16,5],[14,3,19]]
houses =
3
0
1
2
red
blue
green
17
16
14
2
16
3
17
5
19
calls: 0
neighbors can never share a color; find the cheapest paint job
houses =
3
0
1
2
red
blue
green
17
16
14
2
16
3
17
5
19
calls: 0
neighbors can never share a color; find the cheapest paint job
houses =
3
0
1
2
red
blue
green
17
16
14
2
16
3
17
5
19
i = 2
calls: 3
red
=
14
+ min(
,
) =
houses =
3
0
1
2
red
blue
green
17
16
14
14
2
30
16
3
17
5
19
19
i = 1
calls: 5
house 1
each color adds the cheaper of the OTHER two
houses =
3
0
1
2
red
blue
green
25
17
16
14
14
2
30
16
3
3
17
8
5
19
19
i = 0
calls: 7
red
=
17
+ min(
8
,
) =
25
houses =
3
0
1
2
red
blue
green
25
17
16
14
14
2
30
16
3
3
17
8
5
19
19
i = 2
calls: 10
house 2
each color adds the cheaper of the OTHER two
houses =
3
0
1
2
red
blue
green
25
17
19
16
14
14
2
30
16
3
3
17
8
5
19
19
i = 1
calls: 12
green
=
5
+ min(
3
,
19
) =
19
houses =
3
0
1
2
red
blue
green
25
17
19
16
14
14
10
2
30
16
3
3
17
8
5
19
19
i = 0
calls: 14
blue
=
2
+ min(
19
,
) =
10
houses =
3
0
1
2
red
blue
green
25
17
19
16
14
14
10
2
30
16
3
3
17
8
5
19
19
i = 2
calls: 17
house 0: each color costs its own paint,
19
/
8
/
houses =
3
0
1
2
red
blue
green
25
17
19
16
14
14
10
2
30
16
3
3
17
8
5
19
19
i = 2
calls: 20
red
=
14
+ min(
19
,
) =
19
houses =
3
0
1
2
red
blue
green
25
17
19
16
14
14
10
2
30
16
3
3
36
17
8
5
19
19
calls: 21
min cost =
10
=
2
+
5
+
3
algo
master
.
io
Step:
Paint every house red, blue, or green. Neighbors can never match. Minimize the total cost
0 / 74
Input
Example 1
Single house
4 houses
Custom
costs
=
[[17,2,17],[16,16,5],[14,3,19]]
0 / 74
algo
master
.
io
Step:
Paint every house red, blue, or green. Neighbors can never match. Minimize the total cost
