Path paving ways
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.
Implement
count_paving_designs(n: int) → intExamples
in
[2]out3in
[4]out11What a strong answer looks like
State your approach and its time/space complexity out loud before you optimize. Handle the edge cases (empty input, duplicates, overflow), and say why you chose this over the brute force. Green tests are the floor, not the grade.
0:00 of about 12 min
solution.py
InputExpectedGot
[2]3not run yetsample[4]11not run yetsample