Climbing Stairs

easy

You are climbing a staircase. It takes n steps to reach the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Test Cases

Copy an input into the main harness and Run to verify

Input

n = 2

Expected Output

2

Explanation: 1 step + 1 step, or 2 steps.

Input

n = 3

Expected Output

3

Explanation: 1+1+1, 1+2, 2+1.

Hint 1 — click to reveal

ways(n) = ways(n-1) + ways(n-2). Why?

Hint 2 — click to reveal

Recognize the Fibonacci pattern — keep only two variables.

Java Compiler