Climbing Stairs

You are climbing a staircase. It takes n steps to reach the top. Each time you can climb either 1 or 2 steps. Return how many distinct ways you can climb to the top.

Function signature

func ClimbStairs(n int) int

Example

n = 5
output = 8

Constraints

• 1 <= n <= 45

Notes

• This is the Fibonacci sequence with base cases n=1, n=2.