Stair Climbing

De combien de manières uniques pouvez-vous monter au sommet d'un escalier de n marches si vous n'êtes autorisé à monter que 1 ou 2 marches à la fois ?

Exemple 1 :

Entrée : n = 2

Sortie : 2

Explication : Pour monter au sommet d'un escalier de 2 marches, vous pouvez soit monter 1 marche deux fois, soit monter 2 marches d'un coup. Ainsi, il y a 2 manières distinctes de monter au sommet.

Exemple 2 :

Entrée : n = 3

Sortie : 3

Explication : Pour monter au sommet d'un escalier de 3 marches, vous pouvez monter 1 marche trois fois, monter 1 marche puis 2 marches, ou monter 2 marches puis 1 marche. Ainsi, il y a 3 manières distinctes de monter au sommet.

Exemple 3 :

Entrée : n = 4

Sortie : 5

Explication : Pour monter au sommet d'un escalier de 4 marches, voici les 5 options : 1, 1, 1, 1, 1, 1, 2, 1, 2, 1, 2, 1, 1, 2, 2. Où chaque nombre représente une montée de 1 ou 2 marches à la fois, et l'ordre compte.