Why is Climbing Stairs the same as the Fibonacci numbers?

Both follow the rule "each value is the sum of the two before it". Only the start differs: with the Fibonacci sequence 0, 1, 1, 2, 3, 5, ... the number of ways to climb n steps is the Fibonacci number at position n + 1. For example, 12 steps give 233, which is the Fibonacci number at position 13.

What if you can climb 1, 2 or 3 steps at a time?

Sum over every allowed step instead of just two. Pass the steps as a list and fill a table from the bottom: ways = [1] + [0] * n, then for each i from 1 to n set ways[i] = sum(ways[i - s] for s in steps if s <= i) and return ways[n]. With steps = [1, 2, 3], 4 stairs give 7 ways and 6 stairs give 24; with [1, 2] it matches the answers above (4 stairs give 5).

Does it work for a very large number of steps?

The two-variable loop does. Python integers have no fixed size, so nothing overflows: climb_stairs(100) returns 573147844013817084101 and climb_stairs(1000) is a 209-digit number. The memoized version recurses once per step, so a fresh call like climb_stairs(5000) raises RecursionError under the default limit of 1000.

What should climb_stairs(0) return?

All three versions return 1: there is exactly one way to climb zero steps, which is to make no moves. That is also why the recurrence starts from 1 and 1 rather than 0 and 1. If your caller treats zero steps as invalid, check for it before calling.

Can I keep the whole table instead of two variables?

Yes. Build ways = [1, 1] and append ways[-1] + ways[-2] until it has n + 1 entries, then return ways[n]. It is still O(n) time, but O(n) space, so only do it when you need every count along the way, for example to print the answer for each step.

Climbing Stairs: Solution Explained in 15 Languages

Q: Does it work for a very large number of steps?

The two-variable loop does. Python integers have no fixed size, so nothing overflows: climb_stairs(100) returns 573147844013817084101 and climb_stairs(1000) is a 209-digit number. The memoized version recurses once per step, so a fresh call like climb_stairs(5000) raises RecursionError under the default limit of 1000.

Q: What should climb_stairs(0) return?

All three versions return 1: there is exactly one way to climb zero steps, which is to make no moves. That is also why the recurrence starts from 1 and 1 rather than 0 and 1. If your caller treats zero steps as invalid, check for it before calling.

Q: Can I keep the whole table instead of two variables?

Yes. Build ways = [1, 1] and append ways[-1] + ways[-2] until it has n + 1 entries, then return ways[n]. It is still O(n) time, but O(n) space, so only do it when you need every count along the way, for example to print the answer for each step.

climb_stairs.py

Python 3.14

Not run yet

+ 7 hidden

Input

n = 4

Expected

The five sequences are 1+1+1+1, 1+1+2, 1+2+1, 2+1+1 and 2+2.