Montée d'un escalier

Soit $E(n)$ le nombre de façons. Pour atteindre la marche $n$, on vient soit de la marche $n-1$, soit de la marche $n-2$ : donc $E(n)=E(n-1)+E(n-2)$ avec $E(0)=E(1)=1$. C'est la suite de Fibonacci.

def monter_escalier(n):
    a, b = 1, 1
    for _ in range(n):
        a, b = b, a + b
    return a

La complexité est $O(n)$.