Staircase paths avoiding broken steps
Your task
A staircase has steps numbered 1 through n, and you start on the ground (position 0). Each move climbs 1 or 2 steps. Some steps are broken and cannot be landed on; their numbers are given in the list broken (all values are between 1 and n, no duplicates). Return the number of distinct ways to reach step n exactly without ever landing on a broken step. If step n itself is broken, return 0.
Examples
count_safe_paths(n: int, broken: list[int]) -> intExample 1
Input
count_safe_paths(5, [])Output
8Example 2
Input
count_safe_paths(5, [3])Output
2