Stair Climbing

De quantas maneiras únicas você pode subir até o topo de uma escada com n degraus se você só puder subir 1 ou 2 degraus de cada vez?

Exemplo 1:

Entrada: n = 2

Saída: 2

Explicação: Para subir ao topo de uma escada com 2 degraus, você pode subir 1 degrau duas vezes ou subir 2 degraus de uma vez. Assim, existem 2 maneiras distintas de subir ao topo.

Exemplo 2:

Entrada: n = 3

Saída: 3

Explicação: Para subir ao topo de uma escada com 3 degraus, você pode subir 1 degrau três vezes, subir 1 degrau e depois 2 degraus, ou subir 2 degraus e depois 1 degrau. Assim, existem 3 maneiras distintas de subir ao topo.

Exemplo 3:

Entrada: n = 4

Saída: 5

Explicação: Para subir ao topo de uma escada com 4 degraus, aqui estão as 5 opções: 1, 1, 1, 1, 1, 1, 2, 1, 2, 1, 2, 1, 1, 2, 2. Onde cada número representa uma subida de 1 ou 2 degraus de cada vez, e a ordem importa.