AlgoMaster Logo

Paint House

mediumFrequencyUpdated September 21, 2026

Understanding the Problem

We have a row of houses, and each one needs to be painted either red, blue, or green. No two neighboring houses can share the same color. Each house has its own cost for each color, and we want the cheapest total.

This is a decision-at-each-step problem. At each house, we pick a color, but that choice constrains what the next house can pick. A greedy approach (always picking the cheapest color for the current house) does not work, because a locally cheap choice can force an expensive choice for the next house. We have to account for the downstream effect of each decision.

That downstream effect has a clean structure: the minimum cost to paint house i with color c depends only on the minimum costs of painting house i-1 with the other two colors. This overlapping substructure is what makes dynamic programming a good fit.

Key Constraints:

  • 1 <= n <= 100 → A small upper bound, so even an O(n^2) solution would run instantly. The structure of the problem gives us O(n) regardless.
  • costs[i].length == 3 → Exactly 3 colors. With a fixed, small color count, iterating over all colors at each step is O(1).
  • 1 <= costs[i][j] <= 20 → All costs are positive. The maximum total is bounded by 100 * 20 = 2000, which fits comfortably in a 32-bit integer, so there is no overflow concern.

Approach 1: Brute Force (Recursion)

Intuition

Try every valid coloring and pick the cheapest one. For house 0 we have 3 color choices. For every house after that we have 2 choices, anything except the color used for the house before it. Recursively explore all valid combinations and return the minimum total cost.

This builds a decision tree. The root branches into 3 colors, and every node below it branches into 2. The total number of leaves is 3 * 2^(n-1), which grows exponentially with the number of houses.

Algorithm

  1. Define solve(house, color) as the minimum cost to paint houses house through n-1, given that house is painted color.
  2. Add costs[house][color] for painting the current house.
  3. Base case: if house is the last house (n-1), return that cost.
  4. Otherwise, recurse on the next house with each of the other two colors, and add the smaller of the two results.
  5. Start by calling solve(0, c) for all three colors and return the minimum, since the first house has no previous-color constraint.

Example Walkthrough

Input:

0
1
2
0
17
2
17
1
16
16
5
2
14
3
19
costs

The recursion explores all valid colorings and keeps the cheapest. The branch that starts with house 0 painted blue (cost 2) leads to the answer. From blue, house 1 can be red (16) or green (5); the cheaper continuation comes from green. From green at house 1, house 2 can be red (14) or blue (3); blue is cheaper. That path totals 2 + 5 + 3 = 10. Every other starting color produces a larger total: starting red gives at least 17 + 5 + 3 = 25, and starting green gives at least 17 + 16 + 3 = 36, so the minimum over all branches is 10.

10
result

Code

The cost of this approach is repeated work. The same (house, color) subproblem is recomputed many times across different recursion paths, since the best way to paint the houses from index i onward given a fixed color at i does not depend on how we reached i. Caching each subproblem result, or building the answers bottom-up, removes that repetition.

Approach 2: Dynamic Programming (2D Table)

Intuition

The recursive solution recomputes the same (house, color) state many times. Building the answers bottom-up computes each state once. Define dp[i][c] as the minimum cost to paint houses 0 through i with house i painted color c.

To paint house i with color c, we pay costs[i][c] plus the cheapest way to have painted house i-1 with either of the other two colors:

  • 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 answer is min(dp[n-1][0], dp[n-1][1], dp[n-1][2]).

Algorithm

  1. Create a 2D array dp of size n x 3.
  2. Initialize dp[0][c] = costs[0][c] for each color c (painting the first house has no constraints).
  3. For each house from 1 to n-1, compute dp[i][c] using the recurrence above.
  4. Return the minimum of dp[n-1][0], dp[n-1][1], dp[n-1][2].

Example Walkthrough

1Initialize dp[0]: copy costs for house 0 (no constraints on first house)
0
1
2
0
R=17
17
B=2
2
G=17
17
1
0
0
0
2
0
0
0
1/8

Code

The DP table uses O(n) space, but each row only depends on the row directly before it. Once we have computed row i, every earlier row is dead weight. Keeping only the previous row's three values reduces the space to O(1).

Approach 3: Space-Optimized DP

Intuition

Since each row of the DP table only depends on the previous row, we can replace the entire 2D table with three variables holding the previous house's costs. After processing each house, we overwrite these variables with the new house's costs for the next iteration.

This drops the space from O(n) to O(1) while keeping the O(n) time complexity. The recurrence is unchanged; only the storage shrinks.

Algorithm

  1. Initialize three variables prevRed, prevBlue, prevGreen with the costs of painting house 0.
  2. For each house from 1 to n-1, compute the new costs using the previous values.
  3. Be careful to use temporary variables so that updating one color doesn't corrupt the calculation of another.
  4. Return the minimum of the three final values.

Example Walkthrough

1Initialize: prevRed=17, prevBlue=2, prevGreen=17 (house 0 costs)
0
17
R
1
2
B
2
17
G
1/8

Code