Paint House
Medium · Dynamic Programming · Array · Dynamic Programming
Problem
There are n houses in a row, and each must be painted red, blue or green. Painting house i with color j costs costs[i][j], given as an n x 3 matrix.
No two neighboring houses may have the same color. Return the smallest total cost of painting every house.
Examples
Input: costs = [[8,3,6],[4,9,2],[7,1,5]] Output: 6
Use color 1, then color 2, then color 1 again: 3 + 2 + 1 = 6.
Input: costs = [[5,5,5]] Output: 5
A single house takes any color for 5.
Input: costs = [[1,2,9],[1,9,9]] Output: 3
Both houses want color 0; paying 2 for the first house lets the second take its 1.
Constraints
- len(costs) == n
- len(costs[i]) == 3
- 1 <= n <= 100
- 1 <= costs[i][j] <= 20
Approaches
- Baseline: try every coloring — time O(n · 2^n), space O(n)
Follow-up
The state is "which color the last house has", and three colors keep it tiny. The use cases grow the palette to k colors, where the two cheapest totals stand in for a scan, and count fence colorings that avoid three equal posts in a row.
Related problems
Start free on Cariara · Coding problems · System design studio
