This page uses the site's newer layout, so only the problem statement and the section outline survive in the public payload — open the original for the rest.
Dynamic Programming
Paint House
medium
DESCRIPTION (inspired by Leetcode.com)
You are a renowned painter who is given a task to paint n houses in a row. You can paint each house with one of three colors: Red, Blue, or Green. The cost of painting each house with each color is different and given in a 2D array costs:
-
costs[i][0] = cost of painting house i Red
-
costs[i][1] = cost of painting house i Blue
-
costs[i][2] = cost of painting house i Green
No two neighboring houses can have the same color. Return the minimum cost to paint all houses.
Constraints:
-
1 ≤ n ≤ 100
-
costs[i].length == 3
-
0 ≤ costs[i][j] ≤ 1000
Example 1
Input:
costs = [[8, 4, 15], [10, 7, 3], [6, 9, 12]]
Output:
13
Explanation:
-
House 0: Blue (cost = 4)
-
House 1: Green (cost = 3)
-
House 2: Red (cost = 6)
-
Total = 4 + 3 + 6 = 13
Example 2
Input:
costs = [[5, 8, 6], [19, 14, 13], [7, 5, 12], [14, 5, 9]]
Output:
30
Explanation: Red(5) → Green(13) → Red(7) → Blue(5) = 30