/*
**  The problem could be solved by dynamic problem, if we see the stairs as an array,
**  we could calculate from back to front. Each steps required in a stair to reach top
**  is the sum of next 2 stairs.
**
**  Finally, we would recognize it is just Fibonacci Sequence, the result is merely the
**  nth value in the sequence.
**
*/

int ClimbStairs(int n) 
{  
    int s0 = 1;
    int s1 = 1;

    while(--n > 0)
    {
        int temp = s0 + s1;
        s0 = s1;
        s1 = temp;
    }

    return s1;
}

#include <stdio.h>

int main(int argc, char** argv)
{
    for (int i = 1; i < 22; ++i)
        printf("%d stairs: %d\n", i, ClimbStairs(i));
/*
  1 stairs: 1
  2 stairs: 2
  3 stairs: 3
  4 stairs: 5
  5 stairs: 8
  6 stairs: 13
  7 stairs: 21
  8 stairs: 34
  9 stairs: 55
 10 stairs: 89
 11 stairs: 144
 12 stairs: 233
 13 stairs: 377
 14 stairs: 610
 15 stairs: 987
 16 stairs: 1597
 17 stairs: 2584
 18 stairs: 4181
 19 stairs: 6765
 20 stairs: 10946
 21 stairs: 17711
*/    
    
    return 0;
}