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:

  1. We can solve this problem with O(1) space complexity;
  2. 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: }