AlgoViz
HomeDynamic Programming

Paint House

Medium

Best cost per colour, per house

Problem

Paint houses in a row with 3 colors so no two adjacent share a color, minimizing total cost.

In simple words

For each house pick the cheapest colour that differs from the previous house's colour, carried forward.

The idea

For each house track the cheapest total ending in each of the three colours, where each is that house's cost plus the cheaper of the other two colours from the previous house. Only the last row is ever needed.

The trick

  • Never add the same colour's previous cost — that is the adjacency rule.
  • Answer is the minimum across the final three values.
  • O(n) time, O(1) space.

This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.

17
2
17
0
1
2

Step 1 of 2. Here's the example — [[17,2,17],[16,16,5],[14,3,19]] Values: 17, 2, 17.

1/2
Optimal
timeO(n)spaceO(1)
1dp[i][c]=cost[i][c]+min(dp[i-1][other colors])

Input

array
[17, 2, 17]

Output

answer
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:
costs = [[17,2,17],[16,16,5],[14,3,19]]
Output:
10
Explanation:
Paint 2,5,3 (no two neighbours alike) → 10.

Example 2

Input:
costs = [[7,6,2]]
Output:
2
Explanation:
One house → cheapest colour 2.

Example 3

Input:
costs = [[1,2,3],[1,2,3]]
Output:
4
Explanation:
Alternate colours → 1+3 or 2+... best 4.

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.