Path paving ways
Your task
You are paving a straight 1-by-n path using two kinds of pieces: a 1x1 stone, and a 1x2 paver that comes in two colors (red or blue). Pieces of the same kind and color are interchangeable. Return the number of distinct pavings of the whole path. A path of length 0 counts as 1 (lay nothing). For example, n = 2 has 3 pavings: stone+stone, one red paver, or one blue paver.
Examples
count_paving_designs(n: int) -> intExample 1
Input
count_paving_designs(2)Output
3Example 2
Input
count_paving_designs(4)Output
11