Official

C - 階段を登る方法 / Ways to Climb Stairs Editorial by admin

DeepSeek V3

Overview

This is a dynamic programming problem where Takahashi can climb 1 to 3 steps at a time on a staircase, and we need to find the number of ways to reach the top step while avoiding steps that are being painted.

Analysis

This problem is a variant of the classic dynamic programming (DP) staircase problem. In the standard staircase climbing problem, the number of ways to reach each step is calculated as the sum of the values from 1, 2, and 3 steps before it. However, this problem adds the constraint that “you cannot stop on steps that are being painted.”

A naive recursive approach would have a time complexity of \(O(3^N)\) since there are 3 choices at each step, which is far too slow when \(N\) can be up to \(10^5\). Therefore, we need to use dynamic programming to compute the answer efficiently.

Algorithm

Using dynamic programming, we calculate dp[i] as the number of ways to reach step i. The specific procedure is as follows:

  1. dp[0] = 1 (starting from the ground)
  2. Process each step from i=1 to N in order:
    • If step i is being painted (S[i-1] == ‘#’), then dp[i] = 0 (cannot stop here)
    • Otherwise, dp[i] = dp[i-1] + dp[i-2] + dpi-3

We need to be careful that i-1, i-2, and i-3 do not become negative indices. The final answer is dp[N].

Complexity

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

Implementation Notes

  1. Keep values modulo the MOD value (\(10^9 + 7\))

  2. There is an offset of 1 between the string S indices and the dp array indices (S is 0-indexed, while step numbers are 1-indexed)

  3. Before adding, verify that i-1, i-2, and i-3 are non-negative to prevent out-of-bounds access

  4. Reset the dp value to 0 for steps being painted (skip using continue)

    Source Code

MOD = 10**9 + 7

def main():
    import sys
    data = sys.stdin.read().splitlines()
    n = int(data[0].strip())
    S = data[1].strip()
    
    dp = [0] * (n + 1)
    dp[0] = 1
    
    for i in range(1, n + 1):
        if S[i - 1] == '#':
            continue
            
        if i - 1 >= 0:
            dp[i] = (dp[i] + dp[i - 1]) % MOD
        if i - 2 >= 0:
            dp[i] = (dp[i] + dp[i - 2]) % MOD
        if i - 3 >= 0:
            dp[i] = (dp[i] + dp[i - 3]) % MOD
            
    print(dp[n] % MOD)

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.