Paving With Colored Slabs
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
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
Two single slabs in the only single color, or one double slab in any of its 3 colors.
Constraints
0 <= length <= 251 <= singles <= 31 <= doubles <= 3
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.
More Dynamic programming problems
- Pell NumbersBeginner
- Savings With InterestBeginner
- Stacked CansBeginner
- Sum of the Last kBeginner
- Take One, Two or ThreeBeginner
- Three Button CalculatorBeginner
- Broken StairsEasy
- Cheapest Toll RouteEasy