Path paving ways

Write codeEasy12 min

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) -> int
Example 1
Inputcount_paving_designs(2)
Output3
Example 2
Inputcount_paving_designs(4)
Output11