Fibonacci series, topdown and bottom up approaches, stairway climbing

Question

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));
                }
            }

Answer 1

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(2ⁿ) 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.

Answer 2

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.