C - 階段を登る方法 / Ways to Climb Stairs Editorial by admin
DeepSeek V3Overview
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:
- dp[0] = 1 (starting from the ground)
- 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
Keep values modulo the MOD value (\(10^9 + 7\))
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)
Before adding, verify that i-1, i-2, and i-3 are non-negative to prevent out-of-bounds access
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.