Paving a Garden Path

Easy · Paving a Garden Path

A garden path `length` cells long has to be paved. There are two kinds of tiles: a short one covers a single cell and a long one covers two neighbouring cells. You have as many tiles of each kind as you need. The whole path must be covered with no gaps and no overlaps. Two layouts are different if the sequences of tiles from the start of the path to its end differ: for example, "long, short" and "short, long" are two different layouts. Return the number of different layouts.…