C - 階段を登る方法 / Ways to Climb Stairs Editorial by admin Editorial for printing
GPT 5.2 HighOverview
On a staircase where you can advance \(1, 2, 3\) steps at a time, count the number of ways to reach step \(N\) while avoiding steps that cannot be stopped on (#), using dynamic programming to find the result modulo \(10^9+7\).
Analysis
The only ways to reach each step \(i\) are “coming from 1 step before, 2 steps before, or 3 steps before.” In other words, the answer for each step can be constructed from the answers of the previous 3 steps.
- Naively “enumerating all climbing patterns” would cause the number of branches to increase by up to 3 at each step, leading to an exponential number of ways, which is far too slow for \(N \le 10^5\) (TLE).
- Also, steps under construction (
#) “can be passed through but cannot be stopped on,” so we must not count those steps as reachable destinations. Handling this carelessly leads to WA.
Therefore, by using DP (dynamic programming) that sequentially computes “the number of ways to reach each step,” we only need to process each step once.
As a concrete example, when step \(i\) is .:
- Go up 1 step from step \(i-1\)
- Go up 2 steps from step \(i-2\)
- Go up 3 steps from step \(i-3\)
We simply add up these 3 “ways of arriving.” If the step is #, we set \(dp[i]=0\).
Algorithm
Define \(dp[i]\) as “the number of ways to reach and stop at step \(i\).”
- Initial value: We are on the ground (step 0) in exactly 1 way, so \(dp[0]=1\)
- Transition:
- If \(S[i] = \#\) (step \(i\) is under construction), we cannot stop there, so \(dp[i]=0\)
- Otherwise (
.): \(dp[i] = dp[i-1] + dp[i-2] + dp[i-3]\) (only for indices that exist)
- Since values can become large, take mod \(10^9+7\) at each computation.
The string \(S\) is given in 0-index for 1-indexed step numbers, so the state of step \(i\) is checked by looking at S[i-1].
Complexity
- Time complexity: \(O(N)\) (a constant number of additions per step)
- Space complexity: \(O(N)\) (storing the array \(dp\))
Implementation Notes
Since
Sis 0-indexed, note that the check for step \(i\) usesS[i-1].Steps with
#“can be passed through but cannot be stopped on,” so as a transition destination they are treated as 0 (dp[i]=0).When \(i<2\) or \(i<3\), avoid referencing
dp[i-2]ordp[i-3]by using conditional branches likeif i >= 2.The final answer is
dp[N]. According to the problem statement, step \(N\) is always., so there is no need to check reachability.Source Code
import sys
MOD = 10**9 + 7
def main():
input = sys.stdin.readline
N = int(input().strip())
S = input().strip()
dp = [0] * (N + 1)
dp[0] = 1
for i in range(1, N + 1):
if S[i - 1] == '#':
dp[i] = 0
continue
val = dp[i - 1]
if i >= 2:
val += dp[i - 2]
if i >= 3:
val += dp[i - 3]
dp[i] = val % MOD
print(dp[N] % MOD)
if __name__ == "__main__":
main()
This editorial was generated by gpt-5.2-high.
posted:
last update: