class Solution:
    def climbStairs(self, n: int) -> int:
        fact = [1]
        for i in range(1, n+1):
            fact.append(fact[i-1]*i)

        l = int(n/2)+1

        ways = 0
        for i in range(l):
            ways += fact[n-i]/fact[i]/fact[n-2*i]

        return int(ways)

def main():
    s = Solution()

    print(s.climbStairs(2)) # 2
    print(s.climbStairs(3)) # 3
    print(s.climbStairs(4)) # 5

if __name__ == '__main__':
    main()
			

O(2^n), memory complexity O(n)

class Solution:
    def climbStairs(self, n: int) -> int:
        if n == 1 or n == 2:
            return n

        return self.climbStairs(n-1) + self.climbStairs(n-2)

def main():
    s = Solution()

    print(s.climbStairs(2)) # 2
    print(s.climbStairs(3)) # 3
    print(s.climbStairs(4)) # 5

if __name__ == '__main__':
    main()
			

Time complexity: O(n)
Memory complexity: O(n)

from typing import List

class Solution:
    def climbStairs(self, n: int) -> int:
        l = [0]*(n+1)

        return self.climb(n, l)

    def climb(self, n: int, l: List[int]) -> int:
        if n == 1 or n == 2:
            return n

        if l[n] > 0:
            return l[n]

        c = self.climb(n-1, l) + self.climb(n-2, l)

        if l[n] == 0:
            l[n] = c

        return c

def main():
    s = Solution()

    print(s.climbStairs(2)) # 2
    print(s.climbStairs(3)) # 3
    print(s.climbStairs(4)) # 5

if __name__ == '__main__':
    main()
			

Time complexity: O(n)
Memory complexity: O(n)

class Solution:
    def climbStairs(self, n: int) -> int:
        l = [0]*(n+1)
        l[1] = 1
        l[2] = 2

        for i in range(3, n+1):
            l[i] = l[i-1] + l[i-2]

        return l[n]

def main():
    s = Solution()

    print(s.climbStairs(2)) # 2
    print(s.climbStairs(3)) # 3
    print(s.climbStairs(4)) # 5

if __name__ == '__main__':
    main()