Challenge: Climbing Stairs

Lab Python Beginner 10 points

You can climb 1 or 2 steps at a time. Print the number of different ways to climb n steps, using a DP table or two variables.

One whole number n (1 ≤ n ≤ 90).

The number of ways.

Input

Output

Sample input available Sample output available

Editor

Python

Hints

ways[i] = ways[i - 1] + ways[i - 2].

ways[0] = ways[1] = 1.

The same pattern as Fibonacci, solved bottom-up in O(n).

Show solution

n = int(input())
a, b = 1, 1
for _ in range(n - 1):
    a, b = b, a + b
print(b)

Output

Answer