Climbing Stairs

Loading...LeetCode

Brute force:

def climb_stairs(n):
    """
    time: O(2^n)
    space: O(n)
    """
    if n <=2:
        return n

    return  climb_stairs_2(n-1) + climb_stairs_2(n-2)

Tabulation:

def climb_stairs(n):
    """
    time: O(n)
    complexity: O(n)
    """
    if n <=2:
        return n

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

Tabulation with better memory usage:

def climb_stairs(n):
    """
    time: O(n)
    complexity: O(1)
    """
    if n <=2:
        return n

    s1 = 1
    s2 = 2
    for i in range(3, n + 1):
        s = s2 + s1
        s1 = s2
        s2 = s
    
    return s2