FunctionRacerProblemsRace

Paving With Colored Slabs

BeginnerDynamic programmingPython, JavaScript, TypeScript, Java, C++

A garden path is one cell wide and length cells long. Single slabs cover one cell and come in singles different colors. Double slabs cover two neighboring cells and come in doubles different colors.

Return the number of ways to pave the whole path with no gaps and no overlaps. Two pavings are different when, read from the start of the path, their slabs differ somewhere in size or color. A path of length 0 has exactly one paving: lay nothing.

Example 1

length 3
singles 2
doubles 1
returns 12

Three single slabs give 2 * 2 * 2 = 8 pavings. One double slab plus one single slab, in either order, gives 2 + 2 = 4 more.

Example 2

length 2
singles 1
doubles 3
returns 4

Two single slabs in the only single color, or one double slab in any of its 3 colors.

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