Bạn đang leo cầu thang. Để leo lên đến đỉnh, bạn cần đi qua n bước.

Mỗi lần bạn chỉ có thể đi một bước hoặc hai bước. Hỏi có bao nhiêu cách riêng biệt để bạn có thể leo lên đến đỉnh?

Ví dụ 1:

Input: n = 2

Output: 2

Giải thích: Có hai cách để leo lên đỉnh.

1 bước + 1 bước

2 bước

Ví dụ 2:

Input: n = 3

Output: 3

Giải thích: Có ba cách để leo lên đỉnh.

1 bước + 1 bước + 1 bước

1 bước + 2 bước

2 bước + 1 bước

Ràng buộc:

1 <= n <= 45

Yêu cầu: Tìm số cách riêng biệt để leo lên đỉnh với n bước đã cho.