DP #36. Staircase Problem - mbhushan/dynpro GitHub Wiki

(36). Staircase Problem - Fibonacci Series:

Given a staircase and give you can take 1 or 2 steps at a time, 
how many ways you can reach nth step.

Approach (recursive):

	public int staircase(int n) {
		if (n == 0 || n == 1) {
			return n;
		}

		int count = 0;
		count += staircase(n-1) + staircase(n-2);
		return count;
		
	}

Approach (DP):

public int staircase(int n) {
	int a = 0;
        int b = 1;

       for (int i=2; i<= n; i++) {
            int c = a + b;
            a = b;
            b = c;		
	}
       return b;
}

* Time Complexity: O(n)
* Space Complexity: O(1)