Introduction

EXAMPLE: Fibonacci Series

• Using Recursion: Fib(n)
  • If n==0, return 0.
  • If n==1, return 1.
  • return fib(n-1) + fib(n-2).

  In this method, the recursive call is made only if n is neither 1 not 0. So there occurs a situation where recursive calls has to be made for same value of n but at different instance.
  Suppose we calculate Fib(4): (i) The recursive calls made in root function are - Fib(3) and Fib(2). (ii) The recursive calls made in Fib(3) are - Fib(2) and Fib(1). (iii) The recursive calls made in Fib(2) are - Fib(1) and Fib(0).
  Notice that the the recursive call for n=2 is made twice here and this situation occurs for other values of n also. The simple solution is to memoize the newly calculated value for n as shown in next step.

• Using DP
  1. Top-Down DP: Fib(n)
     Create a global integer array memo[n].
     • if memo[n]!=NULL, return memo[n].
     • If n==0, return 0.
     • If n==1, return 1.
     • memo[n] = fib(n-1) + fib(n-2).
     • return memo[n].

     Here, we see that if memo[n] is not null then it returns the value stored in it which prevents from making a new recursive call.
     It is top-down dp because the problem is broken into sub problems, each of these sub problems is solved, and the solutions are remembered in case they need to be solved again.

  2. Bottom-Up DP: Fib(n)
     • Let memo[n+1] be an integer array.
     • Initially, memo[0] = 0 and memo[1] = 1.
     • Loop from i=2 to n.
     • memo[i] = memo[i-1] + memo[i-2].
     • return memo[n].

     Here, we see that if memo[n] is calculated just by adding the previous two integers stored in that array.
     It is bottom-up dp because these methods start with lower values of input and keep building the solutions for higher values.

Similar posts: Warshall's Algorithm | Floyd's Algorithm | Knapsack problem