Dynamic Programming

What is dynamic programming?

It is a way of making your algorithm more efficient by storing some of the intermediate results and it works really well when your algorithm has a lot of repetitive computations. So that you don't have to repeat those computations over and over again. 

I'm gonna give you a concrete example of how it works with Fibonacci Sequence (1, 1, 2, 3, 5, 8, ....).

Let see how we can solve the problem using dynamic programming. There are typically three steps you can take:

1. Recursion.

2. Store (Memoize).

3. Bottom-up.

Recursion solution

 public static int fibSeq(int n) {
      // this function return the value of Fibonacci Sequence at n position      
      if(n ==1 || n==2)
           return 1;
      else
           return (fibSeq(n-1) + fibSeq(n-2)); 
         
}
// Let call this function return value 5 fastly
fibSeq(5);

// Return 6765 value pretty quickly on my computer
fibSeq(20);

// Return  value 9227465 it takes 5 to 6 seconds on my computer
fibSeq(35);

So it's obviously not the most efficient.

Memoized solution

public static int fibSeq_2(int n, int[] memo) {
      int result = 0;
      // this function return the value of Fibonacci Sequence at n position 
      if(memo[n] != 0)
           return memo[n];
      if(n == 1 || n == 2)
           result = 1;
      else
           return (fibSeq_2(n-1, memo) + fibSeq_2(n-2, memo)); 
         memo[n] = result;
       return result;
}

public static int fibMemo(n){
      int[] memo = new int[n+1];
      return fibSeq_2(n, memo);
}

// Let call this function return value 5 fastly
fibMemo(5);

// Return  value 9227465 value quickly on my computer
fibSeq(35);

// Return a recursive error
fibSeq(100);

// Return a recursive error
fibSeq(1000);

Because there are too many recursive calls on a call stack and to fix that we can just use the bottom-up approach and the advantage of using a bottom-up approach is that we don't have to put any recursive calls on a call stack. 

Bottom-up solution


public static int fibSeqBottom_up(int n) {
      // this function return the value of Fibonacci Sequence at n position
      if(n == 1 || n == 2)
           return 1;

      int[] bottom_up = new int[n+1];
      bottom_up[1] = 1;
      bottom_up[2] = 1;

      for(int count=0; count < bottom_up.length; count++){
             bottom_up[count] = bottom_up[count-1] + bottom_up[count-2];
      }
      return bottom_up[n];
}

// Let call this function

// Return a 9227465 value quickly on my computer
fibSeqBottom_up(35);

// Return a 1556111435 value pretty quickly on my computer
fibSeqBottom_up(1000);

// pretty instantaneous
fibSeqBottom_up(10000);