# def climbStairs(n: int) -> int:
#     if n < 1 or n > 45:
#         return 0
#     else:
#         a = 1
#         b = 1
#         for i in range(2, n + 1):
#             a, b = b, a + b
#         return b

# print(climbStairs(4))

def f(n):
    cach = {}
    def g(n):
        if n == 1:
            return 1
        if n == 2:
            return 2
        else:
            if n-1 in cach:
                f1 = cach[n-1]
            else:
                f1 = g(n-1)
                cach[n-1] = f1
            if n-2 in cach:
                f2 = cach[n-2]
            else:
                f2 = g(n-2)
                cach[n-2] = f2
        return f1 + f2
    return g(n)

print(f(4))