You are climbing a stair case. Each time you can either make 1 step or 2 steps. The staircase has n steps. In how many distinct ways can you climb the staircase?
This problem has a dynamic programming solution with the following recurrence:
L[i] = L[i-1] + L[i-2] where L[i] stores the number of distinct ways to climb i stairs. Solution has O(n) complexity.
We can make two observations:
- We can solve this problem with O(1) space complexity;
- This is the Fibonacci recurrence.