Given n stairs and a set of broken steps that cannot be stepped on, return the number of ways to reach the top using 1 or 2 steps at a time. Pattern focus: Climbing stairs. This adds forbidden states to the classic recurrence and tests edge handling.
n = total stairs, broken = array of forbidden stair numbers
number of valid ways to reach the top
Example 1:
Input:
n = 4 broken = [2]
Output:
1
Explanation:
The only valid path avoids landing on stair 2.
Example 2:
Input:
n = 5 broken = [3]
Output:
2
Explanation:
There are two valid ways to reach the top without stepping on stair 3.