Escalier
Vous montez un escalier avec
n marches. À chaque pas, vous pouvez soit gravir 2 marches, soit n’en gravir qu’une seule. Combien de manières différentes existe-t-il pour monter jusqu’en haut ?Entrée
L’entrée contient un seul entier
n (1 ≤ n ≤ 45).Sortie
La sortie doit afficher le nombre de façons différentes de monter cet escalier.
Exemples
Entrée | Sortie |
2 | 2 |
3 | 3 |
Explication
- Pour 2 marches → (1) 1 marche + 1 marche. (2) 2 marches
- Pour 3 marches → (1) 1 marche + 1 marche + 1 marche. (2) 1 marche + 2 marches. (3) 2 marches + 1 marche
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB