Bottom Up vs Top Down Coding Techniques

First time i was working on Dynamic programming, i was confuse by this Bottom up and top down approach and what it really means.  Later after spending some time with it, this is what i understood. Although these approaches has nothing to do with Dynamic Programming but these terminologies mostly heard when we work on DP problems. 

Lets take fibonacci series as an example

1,1,2,3,5,8,13,21....

first number: 1
Second number: 1
Third Number: 2

Another way to put it,

Bottom(first) number: 1
Top (Eighth) number on the given sequence: 21

In case of first five fibonacci number

Bottom(first) number :1
Top (fifth) number: 5 

Now lets take a look of recursive Fibonacci series algorithm as an example

public int rcursive(int n) {
    if ((n == 1) || (n == 2)) {
        return 1;
    } else {
        return rcursive(n - 1) + rcursive(n - 2);
    }
}

Now if we execute this program with following commands

rcursive(5);

if we closely look into the algorithm, in-order to generate fifth number it requires 3rd and 4th numbers. So my recursion actually start from top(5) and then goes all the way to bottom/lower numbers. This approach is actually top-down approach. We can even say this is Top Down recursive approach. 

Bottom-Up

But, question is, can we start from bottom, like from first fibonacci number then walk our way to up. Lets rewrite it using this techniques,

public int fibonacci(int n) {
        int first = 1; //first fibonacci number
        int seccond = 1; //seccond fibonacci number
        int count = 2;
        int result = 0;
        int temp;
        if ((n == 1) || (n == 2)) {
            return 1;
        }
        while (count < n) {
            result = first + seccond;
            temp = seccond;
            seccond = result;
            first = temp;
            count++;
        }
        return result;
}

Now if we look into this algorithm it actually start from lower values then go to top. If i need 5th fibonacci number i am actually calculating 1st, then second then third all the way to up 5th number. This techniques actually called bottom-up techniques.

Last two, algorithms meet the criteria of generating Nth Fibonacci series. But one is top-down and another one is bottom-up.

To avoid doing same calculation multiple times we can reuse some previously calculated values. We store previously store and reuse it. This technique is called memoization. In next part, i am improving recursive approach by this techniques. 

Top-Down (Memoized)

Lets rewrite our original recursive algorithm and add memoized techniques.

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

And we execute this method like following

   int n = 5;
    int[] memo = new int[n + 1];
    Arrays.fill(memo, -1);
    memoized(n, memo);

This solution is still top-down as algorithm start from top value and go to bottom each step to get our top value.

Bottom-Up (Memoized)

But, question is, can we start from bottom, like from first fibonacci number then walk our way to up. Lets rewrite it using this techniques,

public int dp(int n) {
    int[] output = new int[n + 1];
    output[1] = 1;
    output[2] = 1;
    for (int i = 3; i <= n; i++) {
        output[i] = output[i - 1] + output[i - 2];
    }
    return output[n];
}

Now if we look into this algorithm it actually start from lower values then go to top. If i need 5th fibonacci number i am actually calculating 1st, then second then third all the way to up 5th number. This techniques actually called bottom-up techniques.