Counting ways to climb up the stairs-CodePudding

"You are climbing a staircase. It takes n steps to reach the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?"

I saw this question on leetcode and I was trying to work it out using recursive way. I am not sure if this is the proper approach but I still gave it a try. Can someone please help me and tell me if this is even a right approach?

WAYS = 0   # global variable?

def climb_stairs(n):
    if n == 0:
        WAYS  = 1
        return
    else:
        climb_stairs(n-1)
        if n % 2 == 0:
            climb_stairs(n-2)
    return WAYS

CodePudding user response：

IIUC, you simply need to use:

def climb_stairs(n): # n > 0
    if n <= 2:
        return n # if 2 steps, 2 ways (1 or 2), else only 1
    else:
        # if we chose 1, then there are n-1 steps left
        # if we chose 2, then there are n-2 steps left
        return climb_stairs(n-1) climb_stairs(n-2)

climb_stairs(2)
# 2 (1 1 or 2)

climb_stairs(5)
# 8 (1 1 1 1 1, 2 1 1 1, 1 2 1 1, 1 1 2 1, 1 1 1 2, 2 2 1, 2 1 2, 1 2 2)

complexity

I assumed the question was before all a coding training. If you want to improve efficiency you can use a cache, wuch as functools.lru_cache (or functools.cache for python ≥ 3.9):

from functools import lru_cache

@lru_cache(maxsize=None)
def climb_stairs(n):
    if n <= 2:
        return n # if 2 steps, 2 ways (1 or 2), else only 1
    else:
        return climb_stairs(n-1) climb_stairs(n-2)
    
climb_stairs(40)
# 165580141

CodePudding user response：

This is far from optimal solution - the complexity will be O(2^n). To achieve an optimal programatic solution you should use DP / memoization:

def climb_stairs_updated(n):
    climb_stairs_updated.counter  = 1
    if n <= 2:
        memoization[n] = n
        return n
    if n in memoization:
        return memoization[n]
    else:
        result = climb_stairs_updated(n-1)   climb_stairs_updated(n-2)
        memoization[n] = result
        return result
    
memoization = {}
climb_stairs_updated.counter = 0
climb_stairs_updated(5)

The counter in the function counts the call for evaluation purposes - the solution is in O(n).