Tiling a Two by N Strip
You have a strip 2 cells tall and n cells wide, and unlimited dominoes of size 1 by 2 that may be placed lying down or standing up. Return the number of different ways to cover the whole strip with no overlaps.
Example 1
n 3
returns 3
Three ways: three vertical, or one vertical plus a pair of horizontals on either side.
Constraints
1 <= n <= 30
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.
More Dynamic programming problems
- Token Orders at the TurnstileEasy
- Two-Lane RoadEasy
- Best Stretch SumMedium
- Cheapest DescentMedium
- Cheapest Pool PassesMedium
- Coins From Either EndMedium
- Count DerangementsMedium
- Count the Free PlotsMedium