Climbing Stairs

You're climbing a staircase with n steps. Each move you can climb either 1 or 2 steps. In how many distinct ways can you reach the top?

Example

Input: n = 5 Output: 8

Approach

The number of ways to reach step n is the sum of the ways to reach step n-1 (then take one step) and step n-2 (then take two steps) — this is exactly the Fibonacci recurrence, computable bottom-up in O(n) time and O(1) space instead of exponential naive recursion.

Walkthrough

1n = int(input())
2if n <= 2:
3    print(n)
4else:
5    a, b = 1, 2
6    for _ in range(3, n + 1):
7        a, b = b, a + b
8    print(b)

Input format

Line 1: n

Print the number of distinct ways.