Staircase Climb Ways

Problem: Staircase Climb Ways

Imagine you are on an Easter-themed adventure this April 7, 2025. You are given a staircase with n steps numbered from 1 to n. Some of these steps are broken (represented as a list of integers). Your goal is to count the number of distinct ways to reach the top (step n) starting from step 1, under the following rules:

• You can move either 1 or 2 steps at a time.
• You cannot stand on a broken step.
• The first (step 1) and the last (step n) steps are always intact.

Input

• n: A positive integer indicating the total number of steps.
• broken_steps: A list/array of integers representing the steps that are broken (excluding step 1 and step n).

Output

• An integer representing the total number of ways to safely climb from step 1 to step n.

Example

For instance, if n = 5 and broken_steps = [3], then the valid sequence could be:

• 1 → 2 → 4 → 5

There might be other sequences, but any path that steps on 3 must be disregarded. Use a dynamic programming approach to count all valid ways.

Hint: Think about how you can utilize the results of previous steps (subproblems) to compute the result for the current step.

Good luck!