Three-Colour Street

Medium

Houses stand in a row along a street, and each must be painted one of three colours. prices[i][j] is the cost of painting house i in colour j (colours are numbered 0, 1, 2). Neighbouring houses must not have the same colour. Return the minimum total cost of painting every house.

Example 1

prices=[[4, 9, 2], [3, 8, 5], [6, 1, 7]] → 6

Colour 3 for house 0 (2), colour 1 for house 1 (3), colour 2 for house 2 (1): 2 + 3 + 1 = 6.

Example 2

prices=[[5, 1, 5], [5, 1, 5]] → 6

Colour 2 is cheapest for both houses, but neighbours cannot share it: 1 + 5 = 6.

Example 3

prices=[[12, 3, 8]] → 3

Constraints

1 ≤ len(prices) ≤ 100
len(prices[i]) = 3
1 ≤ prices[i][j] ≤ 20

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Dynamic Programming

Similar problems

Fewest Jumps to the End Medium Most Profitable Streak Medium Reach the Last Cell Medium Warehouse Cart Routes Medium Cheapest Corner-to-Corner Route Medium

Input

prices=[[4, 9, 2], [3, 8, 5], [6, 1, 7]]

Expected

Run checks the first 3 tests in your browser. Submit checks all 85 tests on the server, hidden ones included.