Paint the Street, No Matching Neighbors

Hard

A row of houses lines a street, and each must be painted in one of k colors. Prices differ: prices[i][c] is the cost of painting house i in color c. No two neighboring houses may share a color. Return the lowest total cost of painting every house. Try to stay within O(n·k), where n is the number of houses.

Example 1

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

House 0 in color 1 (1), house 1 in color 0 (2), house 2 in color 1 again (1): 4 in total, and no two neighbors match.

Example 2

prices=[[1, 2], [1, 2], [1, 2]] → 4

Color 0 is cheaper, but neighbors cannot match: 1 + 2 + 1 = 4.

Example 3

prices=[[6, 3, 9, 2]] → 2

Constraints

1 ≤ n = len(prices) ≤ 100
2 ≤ k = len(prices[i]) ≤ 20, all rows have the same length
1 ≤ prices[i][c] ≤ 20

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Dynamic Programming

Similar problems

Water Between Walls Hard Biggest Solid Panel Block Hard Profit From Two Trades Hard Every Way to Space the Words Hard Crossing the Cave Hard

Input

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

Expected

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