公式

C - 階段を登る方法 / Ways to Climb Stairs 解説 by admin 印刷ページ

Qwen3-Coder-480B

Overview

This is a problem where you can climb a staircase of \(N\) steps by going up 1, 2, or 3 steps at a time, with the constraint that you cannot stop on certain steps. The goal is to find the total number of ways to reach the top step.

Approach

This problem can be solved using typical dynamic programming (DP).

First, without any constraints, the number of ways to reach step \(i\) can be expressed as: $\( \text{dp}[i] = \text{dp}[i-1] + \text{dp}[i-2] + \text{dp}[i-3] \)\( This is because you can reach step \)i$ in one jump from 1 step before, 2 steps before, or 3 steps before.

However, in this problem, “you cannot stop on certain steps,” meaning you cannot land on steps marked with #. Therefore, \(\text{dp}[i]\) for those steps must not be updated.

Specifically: - If \(S[i-1] == \text{`#'}\), you cannot stop on that step, so \(\text{dp}[i]\) remains \(0\). - Otherwise (.), perform the transition as usual.

Also, as an initial condition, we set \(\text{dp}[0] = 1\). This represents “there is exactly one way to start from the ground.”

In this way, \(\text{dp}[N]\) gives us the final answer.

Algorithm

We use dynamic programming (DP).

  • \(\text{dp}[i]\): the number of ways to reach step \(i\)
  • Initialization: \(\text{dp}[0] = 1\)
  • Update:
    • For each step \(i = 1\) to \(N\):
      • If \(S[i-1] == \text{`#'}\), skip
      • Otherwise, $\( \text{dp}[i] = (\text{dp}[i] + \text{dp}[i-1] + \text{dp}[i-2] + \text{dp}[i-3]) \bmod (10^9+7) \)$ (only for indices that are non-negative)

In this way, we simply output \(\text{dp}[N]\) as the final answer.

Example

For example, when \(N=4\), \(S=\text{"..#."}\):

Step State dp value
0 - 1
1 . 1
2 . 2
3 # 0
4 . 3

Therefore, the answer is \(3\) ways.

Complexity

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

Since we perform only constant-time operations for each step, the problem can be solved in linear time. The array uses only \(N+1\) elements, so the space is also linear.

Implementation Notes

  • Since the string \(S\) uses 0-based indexing, step \(i\) corresponds to \(S[i-1]\).
  • The answer must be output modulo \(10^9+7\), so make sure to take the mod at appropriate points.
  • The key point is to initialize the entire DP table to 0 and then set \(\text{dp}[0] = 1\).
## Source Code

```python
MOD = 10**9 + 7

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    N = int(data[0])
    S = data[1]
    
    # dp[i] := i段目に到達する方法の数
    dp = [0] * (N + 1)
    dp[0] = 1
    
    for i in range(1, N + 1):
        if S[i-1] == '#':
            continue
        for step in range(1, 4):
            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.

投稿日時:
最終更新: