Dynamic programming · routine

Climbing stairs

You climb a staircase taking 1 or 2 steps at a time. Write ways(n) returning how many different ways reach step n. ways(0) and ways(1) are 1; ways(3) is 3.

To stand on step n you came from n − 1 or n − 2, so ways(n) = ways(n - 1) + ways(n - 2). Written like that it recomputes the same answers over and over.

right answers
arguments left as they should be
fast enough at scale
without lru_cache, cache, functools

def ways(n):
    if n <= 1:
        return 1
    return ways(n - 1) + ways(n - 2)

Run adds print(ways(10)) after your code, to try it.

Stuck on the idea rather than the code? The Dynamic programming lesson walks through it.