Solutions

# At each step, the ways of climbing are ways(s-1) + ways(s-2). Base cases 0, 1, 2. Top-down or bottom-up DP. 
# dp

# Top-down DP: O(n) time, O(n) space (would be 2^n without memoization)
def climbStairs(n: int) -> int:
    cache = {}

    def dfs(s: int) -> int:
        if s <= 2:
            return s
        if s in cache:
            return cache[s]
        cache[s] = dfs(s-1) + dfs(s-2)
        return cache[s]

    return dfs(n)

# Top-down DP reversed: O(n) time, O(n) space
def climbStairs(n: int) -> int:
    cache = {}

    def dfs(s: int) -> int:
        if s == n:
            return 1
        if s > n:
            return 0
        if s in cache:
            return cache[s]
        cache[s] = dfs(s+1) + dfs(s+2)
        return cache[s]
    return dfs(0)

# Bottom-up DP: O(n) time, O(n) space
def climbStairs(n: int) -> int:
    if n <= 2:
        return n

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

    return dp[n]


# Bottom-up DP optimized: O(n) time, O(1) space
def climbStairs(n: int) -> int:
    if n <= 2:
        return n

    one = 1
    two = 1
    for _ in range(n -1):
        temp = one
        one = one + two
        two = temp
    return one