FunctionRacerProblemsRace

Paint the Sheds

EasyDynamic programmingPython, JavaScript, TypeScript, Java, C++

A row of sheds must be painted, each in a single color, and two neighboring sheds may never have the same color. costs[i][c] is the price of painting shed i with color c; every shed offers the same colors, at least two of them.

Return the smallest total price of painting every shed. An empty row costs 0.

Example 1

costs [[1,5,6],[2,9,9],[8,1,7]]
returns 8

Paint shed 0 with color 1 (5), shed 1 with color 0 (2) and shed 2 with color 1 (1). Taking the cheap color 0 for shed 0 forces a 9 on shed 1.

Example 2

costs [[3,1],[4,2],[6,5]]
returns 10

With two colors the sheds must alternate. Colors 1, 0, 1 cost 1 + 4 + 5 = 10; colors 0, 1, 0 cost 11.

Constraints

Race itor take your time

Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.

More Dynamic programming problems