Climbing stairs python - big numbers

Question

what this code should do is you have to climb a staircase with 'n' steps. At each step, you can either climb '1' or '2' steps. this code works with small numbers but not with big numbers, for exemple print(climbing_stairs(45)) won't work. In C there are long and double long, i was wondering if there is something similar in python.

    def climbing_stairs(n):
            if ( n == 0 ):
                    return 1
                elif (n < 0):
                    return 0
             
                else:
                    return climbing_stairs(n - 2) + climbing_stairs(n - 1)
        
print(climbing_stairs(2))
print(climbing_stairs(3))
print(climbing_stairs(45))

Answer 1

The problem with the current code is the run time complexity. This code runs in O(2^n) and it isn't feasible for larger numbers.

This problem is just a rewording of the Fibonacci numbers. What you are currently doing is to recalculate similar results repeatedly. Say, you know how many ways you can move from step 4 to n. When you don't memoize it, you will recalculate it the next time since there are different ways to reach step 4.

dp = {}
def climbing_stairs(n):
    if n == 0 or n == 1:
        return 1
    elif n < 0:
        return 0
    elif n in dp:
        return dp[n]
    else:
        dp[n] = climbing_stairs(n - 2) + climbing_stairs(n - 1)
        return dp[n]

In a more pythonic way:

from functools import cache

@cache
def climbing_stairs(n):
    if n == 0 or n == 1:
        return 1
    elif n < 0:
        return 0
    else:
        return climbing_stairs(n - 2) + climbing_stairs(n - 1)

And there is also an elegant iterative approach to this problem that has a constant time complexity:

def climbing_stairs(n):
    if n < 3: return n
    
    first, second = 1, 2
    for _ in range(1, n):
        third = first+second
        first, second = second, third
    
    return second

Both the memoized recursive version and the iterative one have a linear runtime complexity, since we only calculate the each step once.