Overview

Given a staircase with \(N\) steps where you can climb 1, 2, or 3 steps in a single move, but some steps are broken, find the number of ways to reach step \(N\) from step 0.

Analysis

This problem is a classic application of dynamic programming (DP).

First, for each non-broken step, we can compute “the number of ways to reach that step” in order. For example, to reach step \(i\), we can come from steps \(i-1\), \(i-2\), or \(i-3\). Therefore, the following transition can be considered:

\[ dp[i] = dp[i-1] + dp[i-2] + dp[i-3] \]

However, if step \(i\) is broken, we cannot land on it, so we need to set \(dp[i] = 0\).

Also, it is important to note that even if there are broken steps, we can jump over them. In other words, stopping on a broken step is forbidden, but passing over it is possible.

For example, even if step 2 is broken, it is possible to move directly from step 0 to step 3.

Problems of this type, where we consider “transitions from previous states to the next state,” can be solved efficiently using DP.

A naive recursive approach would result in exponential time, so a bottom-up DP approach is necessary.

Algorithm

We use Dynamic Programming.

• dp[i]: the number of ways to reach step \(i\)
• Initial condition: dp[0] = 1 (there is exactly 1 way to be on the ground)
• Transition:
  • For each step \(i = 1\) to \(N\):
    • If step \(i\) is broken, continue
    • Otherwise, transitions from \(i-1\), \(i-2\), \(i-3\) are possible: $\( dp[i] = (dp[i] + dp[i - 1] + dp[i - 2] + dp[i - 3]) \bmod (10^9 + 7) \)$

The final answer we want is dp[N].

By storing the broken steps in a set beforehand, we can check each step in \(O(1)\).

Complexity

• Time complexity: \(O(N)\)
• Space complexity: \(O(N)\)

Since \(N\) is at most \(10^5\), this is sufficiently fast.

Implementation Notes

• Storing the broken steps in a set allows for fast existence checks.

• The DP table should be allocated from index \(0\) to \(N\).

• When referencing the DP values of the previous 3 steps for each step, be careful about out-of-bounds access (i - step >= 0).

• The final result is dp[N].

  Source Code

MOD = 10**9 + 7

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    M = int(data[1])
    
    if M == 0:
        broken = set()
        idx = 2
    else:
        broken = set(map(int, data[2:2+M]))
        idx = 2 + M
    
    # dp[i] := i段目に到達する方法の数
    dp = [0] * (N + 1)
    dp[0] = 1
    
    for i in range(1, N + 1):
        if i in broken:
            continue
        for step in [1, 2, 3]:
            if i - step >= 0:
                dp[i] = (dp[i] + dp[i - step]) % MOD
    
    print(dp[N])

if __name__ == "__main__":
    main()

---

This editorial was generated by qwen3-coder-480b.