Salire le scale

Quanti metodi distinti puoi usare per raggiungere la cima di una scala con n gradini, se puoi salire solo di 1 o 2 gradini alla volta?

Esempio 1:

Input: n = 2

Output: 2

Spiegazione: Per raggiungere la cima di una scala con 2 gradini, puoi salire di 1 gradino due volte oppure di 2 gradini in una volta sola. Quindi, ci sono 2 modi distinti per raggiungere la cima.

Esempio 2:

Input: n = 3

Output: 3

Spiegazione: Per raggiungere la cima di una scala con 3 gradini, puoi salire di 1 gradino tre volte, salire di 1 gradino e poi di 2 gradini, oppure salire di 2 gradini e poi di 1 gradino. Quindi, ci sono 3 modi distinti per raggiungere la cima.

Esempio 3:

Input: n = 4

Output: 5

Spiegazione: Per raggiungere la cima di una scala con 4 gradini, ecco 5 possibilità: 1, 1, 1, 1, 1, 1, 2, 1, 2, 1, 2, 1, 1, 2, 2. Ogni numero rappresenta una salita di 1 o 2 gradini alla volta e l'ordine è importante.