Programa de Python para contar formas de llegar a la escalera n

Hay n escaleras, una persona parada en la parte inferior quiere llegar a la cima. La persona puede subir 1 o 2 escalones a la vez. Cuente el número de formas en que la persona puede llegar a la cima.
 

Considere el ejemplo que se muestra en el diagrama. El valor de n es 3. Hay 3 formas de llegar a la cima. El diagrama está tomado de los rompecabezas de Fibonacci más fáciles. 
 

# A program to count the number of ways to reach n'th stair
 
# Recurssive program to find n'th fibonacci number
def fib(n):
    if n <= 1:
        return n
    return fib(n-1) + fib(n-2)
 
# returns no. of ways to reach s'th stair
def countWays(s):
    return fib(s + 1)
 
# Driver program
 
s = 4
print ("Number of ways =",countWays(s))
 
# Contributed by Harshit Agrawal

Number of ways =  5

La complejidad temporal de la implementación anterior es exponencial (proporción áurea elevada a la potencia n). Se puede optimizar para que funcione en tiempo O (Logn) utilizando las optimizaciones de funciones de Fibonacci discutidas anteriormente . 
 

# A program to count the number of ways to reach n'th stair
 
# Recursive function used by countWays
def countWaysUtil(n, m):
    if n <= 1:
        return n
    res = 0
    i = 1
    while i<= m and i<= n:
        res = res + countWaysUtil(n-i, m)
        i = i + 1
    return res
     
# Returns number of ways to reach s'th stair   
def countWays(s, m):
    return countWaysUtil(s + 1, m)
     
 
# Driver program
s, m = 4, 2
print ("Number of ways =", countWays(s, m))
 
# Contributed by Harshit Agrawal

Number of ways = 5

Complejidad temporal: O(2 ⁿ )
Espacio auxiliar: O(n)

# A program to count the number of ways to reach n'th stair
 
# Recursive function used by countWays
def countWaysUtil(n, m):
    res = [0 for x in range(n)] # Creates list res with all elements 0
    res[0], res[1] = 1, 1
     
    for i in range(2, n):
        j = 1
        while j<= m and j<= i:
            res[i] = res[i] + res[i-j]
            j = j + 1
    return res[n-1]
 
# Returns number of ways to reach s'th stair
def countWays(s, m):
    return countWaysUtil(s + 1, m)
     
# Driver Program
s, m = 4, 2
print ("Number of ways =", countWays(s, m))
     
# Contributed by Harshit Agrawal

Number of ways = 5

Tiempo Complejidad : O(m*n)

Espacio Auxiliar : O(n)

Consulte el artículo completo sobre las formas de contar para llegar al escalón n para obtener más detalles.