# Fibonacci series, topdown and bottom up approaches, stairway climbing

I have solved fibonacci series and then used the topdown and bottom up approaches to solve it. Also I have included the stairway climbing question as follows "You are climbing a stair case. Each time you can either make 1 step or 2 steps. The staircase has numStairs steps. Returns In how many distinct ways can you climb the staircase." Looking for code review, optimizations, best practices etc.

public final class Fibo {

private Fibo() {}

/**
* Returns the nth number in the fibonacci sequence.
*
* @param n     nth position in the fibo series, which starts from 0th position.
* @return      the nth number in the fibonacci series.
*/
/*
* TimeComplexity: O(n)
* Space Complexity: http://www.geeksforgeeks.org/g-fact-86/
*/
public static int fibo(int n) {
if (n <= 1) return n;
return fibo(n - 1) + fibo(n - 2);
}

/**
* Returns the nth number in the fibonacci sequence.
*
* @param n     nth position in the fibo series, which starts from 0th position.
* @return      the nth number in the fibonacci series.
*/
/*
* Time complexity: O(n)
* Aux Space: O(n)
*/
public static int fiboTopDown(int n) {
if (n < 0) throw new IllegalArgumentException("The value of n: " + n  + " should be positive.");
final Map<Integer, Integer> fiboCache = new HashMap<Integer, Integer>();
return fiboCompute(n, fiboCache);
}

private static int fiboCompute(int n, Map<Integer, Integer> fiboCache) {
if (n <= 1) return n;

if (fiboCache.containsKey(n)) {
return fiboCache.get(n);
}

int sum = fiboCompute (n - 1, fiboCache) + fiboCompute (n - 2, fiboCache);
fiboCache.put(n, sum);

return sum;
}

/**
* Returns the nth number in the fibonacci sequence.
*
* @param n     nth position in the fibo series, which starts from 0th position.
* @return      the nth number in the fibonacci series.
*/
/*
* Time complexity: O(n)
* Aux Space: O(1)
*/
public static int fiboBottomUp(int n) {
if (n < 0) throw new IllegalArgumentException("The value of n: " + n  + " should be positive.");

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

/**
* You are climbing a stair case. Each time you can either make 1 step or 2 steps
* The staircase has numStairs steps. Returns In how many distinct ways can you climb the staircase.
*
* @param numStairs
* @return
*/
public static int stairCount(int numStairs) {
if (numStairs <= 0) throw new IllegalArgumentException("The number of stairs: " + numStairs  + "
should be positive.");
return fiboBottomUp(numStairs + 1);
}

public static void main(String[] args) {

System.out.println(fibo(0) + ":" + fibo(1) + ":" + fibo(2) + ":" + fibo(3) + ":" + fibo(4) + ":" + fibo(5));

System.out.println(fiboTopDown(0) + ":" + fiboTopDown(1) + ":" + fiboTopDown(2) + ":"
+ fiboTopDown(3) + ":" + fiboTopDown(4) + ":" + fiboTopDown(5));

System.out.println(fiboBottomUp(0) + ":" + fiboBottomUp(1) + ":"
+ fiboBottomUp(2) + ":" + fiboBottomUp(3) + ":"
+ fiboBottomUp(4) + ":" + fiboBottomUp(5));

System.out.println(stairCount(1) + ":"
+ stairCount(2) + ":" + stairCount(3) + ":"
+ stairCount(4) + ":" + stairCount(5));
}
}

-

This comment is inaccurate:

/*
* TimeComplexity: O(n)
* Space Complexity: http://www.geeksforgeeks.org/g-fact-86/
*/
public static int fibo(int n) { … }


A naïve recursive fibo() has O(2n) time complexity. Think of it this way: to calculate fibo(n), you break it up into two problems, each of size n - 1.

In fiboBottomUp(), don't declare/define int a = 0, since it is only ever used as a temporary variable inside the for-loop.

public static int fiboBottomUp(int n) {
if (n < 0) {
// Message is inaccurate: n = 0 is allowable
throw new IllegalArgumentException("The value of n: " + n  + " should be non-negative.");
}

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


Using a HashMap<Integer, Integer> for fiboCache is more complicated than necessary. An ArrayList<Integer> or even an int[n + 1] will do, since all the keys are consecutive integers.

Consider widening your return types to long to stave off overflow for a while longer.

-
" Think of it this way: to calculate fibo(n), you break it up into two problems, each of size n - 1.", don't you mean one of size n - 1 and other of size n - 2, though ultimately every fibo(n) produces two problems of size O(n)? – skiwi Jul 13 '14 at 17:40

From a once over:

• The parameter name in stairCount represents the number of steps, maybe it ought to be called numSteps instead of numStairs. Also, personally, I would prefer stepCount.

• There really should be a new line after (numStairs <= 0) to make the code look better

• That could give

public static int stairCount(int stepCount) {
if (stepCount <= 0)
throw new IllegalArgumentException("stepCount should be positive");
return fiboBottomUp(stepCount + 1);
}

• Since you only work with int which is 32 bits, and so can only hold 46 numbers ( 46th is 1836311903 ), you might as well cache all 46 numbers and have your code run super fast.

• This

System.out.println(fiboBottomUp(0) + ":" + fiboBottomUp(1) + ":"
+ fiboBottomUp(2) + ":" + fiboBottomUp(3) + ":"
+ fiboBottomUp(4) + ":" + fiboBottomUp(5));


is begging for a for loop to make it more DRY.

-