You climb a staircase of n steps, taking 1 or 2 steps at a time. How many distinct ways are there to reach the top?
Input
A single integer n.
Output
The number of distinct ways to climb n steps.
Climbing Stairs
Mediumdynamic-programming
Examples
Example 1
- Input
2
- Output
2
1+1 or 2 — two ways.
Example 2
- Input
3
- Output
3
1+1+1, 1+2, 2+1 — three ways.
Example 3
- Input
5
- Output
8
Eight ways.
Constraints
- 1 <= n <= 45
Hints
Reveal hint 1
To reach step n you arrive either from step n-1 (a single step) or step n-2 (a double step).
Reveal hint 2
So ways(n) = ways(n-1) + ways(n-2) — the Fibonacci recurrence.
Reference solution (spoiler — try it yourself first)
Approach
Dynamic programming: ways(1) = 1, ways(2) = 2, ways(n) = ways(n-1) + ways(n-2). Iterate keeping the last two.
n = int(input())
a, b = 1, 1
for _ in range(2, n + 1):
a, b = b, a + b
print(b if n >= 1 else 1)
Bring us the problem, not a perfect specification
Tell us what needs to change, who it affects and any important deadline. We will review the context and reply with useful next questions.
- 01Share contextDescribe the workflow, constraint or risk.
- 02Clarify togetherWe identify missing facts and useful options.
- 03Choose a startAgree a focused assessment or delivery step.