Recursive Staircase Problem

There are n stairs, a person standing at the bottom wants to reach the top. The person can climb either 1 or 2 stairs at a time. Count the number of ways, the person can reach the top.

Solutions

Recursive Solution With Memoization

There are two ways to stair n at a time: a) from stair n-1 in one step or b) from stair n-2 in two steps. Specially, there is: a) 1 way to stair 1 and b) 2 ways to stair 2.

Implementation

from functools import lru_cache

class RecursiveStaircase:
    @lru_cache()
    def solve(self, stair_num):
        if stair_num <= 0: return 0
        if stair_num == 1: return 1
        if stair_num == 2: return 2
        return self.solve(stair_num-1) + self.solve(stair_num-2)