Problem:

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Solution:

The idea behind this problem is the same as Fibonacci which is f(n) = f(n-1) + f(n-2).
There are two solutions making the time complexity as O(N).

1. The first one is an iteration. Time complexity O(n), space complexity O(1).
2. The second one is recurstive version. But the normal recurtion is very expensive, roughly O(2^n).
   So we used dynamic programming by take a buffer stores the value has gone.
   The time complexity is O(n), space complexity is O(n) too.

There are two solutions.
/*

> File Name: ClimbingStairs.java
> Author: Yao Zhang 
> Mail: psyyz10@163.com 
> Created Time: Fri 13 Nov 16:12:24 2015

**/

public class ClimbingStairs{
// Solution 1
public int climbStairs(int n){
if (n <= 1)
return n;

   int prev = 1;
   int last = 1;
   int current = 0;
   for (int i = 2; i <= n; i++){
       current = prev + last;
       last = prev;
       prev = current;
   }

   return current;
}

//Solution2
public int climbStairs(int n){
    if (n < 0) 
        return 0;             

    int[] buffer = new int[n];

    return climbStairsHelper(n, buffer);
}              
public int climbStairsHelper(int n, int[] buffer){
    if (n < 0){
        return 0;
    }else if (n == 0){
        return 1;
    } else if (buffer[n - 1] != 0){                                                                                  
        return buffer[n - 1];        
    } else {   
        buffer[n - 1] = climbStairsHelper(n - 1, buffer) + climbStairsHelper(n - 2, buffer);
        return buffer[n - 1];     
    }          
}   

}