DSA problem
Paint House
There is a row of n houses. Each house can be painted in one of three colors: red, blue, or green. The cost of painting each house with a specific color is given by an n x 3 cost matrix costs. You must paint every house with the constraint that no two adjacent houses share the same color. Return the minimum total cost.
This is a small but instructive DP. Let dp[i][c] be the minimum cost to paint houses 0..i with house i painted color c. The recurrence is dp[i][c] = costs[i][c] + min(dp[i - 1][c']) for c' != c. The base case is the first row: dp[0][c] = costs[0][c].
Because there are exactly three colors, computing the "min over the other two" is constant work. Concretely:
dp[i][0] = costs[i][0] + min(dp[i - 1][1], dp[i - 1][2])dp[i][1] = costs[i][1] + min(dp[i - 1][0], dp[i - 1][2])dp[i][2] = costs[i][2] + min(dp[i - 1][0], dp[i - 1][1])
The final answer is min(dp[n - 1][0], dp[n - 1][1], dp[n - 1][2]). Since each dp[i] depends only on dp[i - 1], we only need three rolling integers a, b, c representing the previous row, updating them in place per house. Total: O(n) time and O(1) extra space. (The same idea generalizes to k colors via "min-and-second-min" tricks.)
Examples
costs = [[17,2,17],[16,16,5],[14,3,19]]10costs = [[7,6,2]]2costs = [[1,2,3],[3,2,1]]2Constraints
- n == costs.length
- costs[i].length == 3
- 1 <= n <= 100
- 0 <= costs[i][j] <= 20
- No two adjacent houses may share the same color.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.