# Staircase climbing with 1 or 2 steps

**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.

1: int stairs(int n) {

2: if (n == 0)

3: return 0;

4: int a = 1;

5: int b = 1;

6: for (int i = 1; i < n; i++) {

7: int c = a;

` 8: a = b;`

` 9: b += c;`

` 10: }`

11: return b;

` 12: }`