Climbing Stairs

You can climb 1 or 2 steps at a time. How many distinct ways are there to climb n steps?

A way to picture it

To be standing on step 10, your very last move was either a small hop from step 9 or a big jump from step 8. So the ways to reach step 10 are just the ways to reach 9 plus the ways to reach 8 — answers you already worked out.

How to approach it

ways(i) = ways(i − 1) + ways(i − 2), with ways(0) = ways(1) = 1. It's Fibonacci, and only the last two values are ever needed.

Example

Input: {"n":2}. Output: 2.

Complexity: O(n) time and O(1) space. One pass keeping two numbers.

This page includes an animated walkthrough, Java and Python solutions, and a question to check your understanding.