Climbing Stairs
Description: You are climbing a staircase with n steps. Each time you can climb either 1 or 2 steps. In how many distinct ways can you reach the top?
Example 1:
Input: n = 5
Output: 8
Explanation: eight distinct ways
Example 2:
Input: n = 2
Output: 2
Explanation: 1+1 and 2
Constraints:
1 <= n <= 45
Recommended time and space complexity
Aim for O(n) time and O(1) space.
Hint 1
Think about where you can arrive at step n from: only from n-1 or n-2.
Hint 2
So ways(n) = ways(n-1) + ways(n-2). Recognise the sequence?
Hint 3
These are Fibonacci numbers. You only need the last two values, not the whole array.