220. Climbing Stairs
Core1000 ms256 MBSolved by 0%
A staircase has n steps. You can climb 1 or 2 steps at a time. Print how
many different ways there are to reach the top.
To arrive at step n you must have come from step n-1 or step n-2, so
the number of ways to reach n is the sum of the ways to reach those two.
You may recognise the recurrence. It is Fibonacci wearing different clothes, which means it has the same problem: written plainly it recomputes the same values exponentially many times.
Constraints - `1 ≤ n ≤ 86` - The answer fits in a signed 64-bit integer.
Input
A single line containing one integer n.
Output
Print one integer, the number of distinct ways to climb the staircase.
Input4
Output5
Noteis small enough to list every route by hand
Input1
Output1
Noteis a single step with only one way to climb it
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.
Hint 1Where to start
Hint 2The approachOpen hint 1 first. This one carries on from it.
Hint 3PseudocodeOpen hint 2 first. This one carries on from it.
Hint 4Full solutionOpen hint 3 first. This one carries on from it.