C - 階段を登る方法 / Ways to Climb Stairs Editorial by admin
Qwen3-Coder-480BOverview
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)
- For each step \(i = 1\) to \(N\):
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.