Skip to content

Dynamic Programming

Divide and Conquer with overlapping results.

Properties

1) Overlapping Subproblems 2) Optimal Substructure

Overlapping Subproblems

subproblems overlap and solutions of them are needed again and again.

Binary Search -> ❎

fibonnici -> ✅

Solutions of same subproblems are needed again and again.

                        fib(5)
                     /             \
               fib(4)                fib(3)
             /      \                /     \
         fib(3)      fib(2)         fib(2)    fib(1)
        /     \        /    \       /    \
  fib(2)   fib(1)  fib(1) fib(0) fib(1) fib(0)
  /    \
fib(1) fib(0)

fib(3) is being called multiple times

Methods

a) Memoization (Top Down)

int fib(int n)  
{  
    if (lookup[n] == NIL)  
    {  
        if (n <= 1)  
            lookup[n] = n;  
        else
            lookup[n] = fib(n - 1) + fib(n - 2);  
}

b) Tabulation (Bottom Up)

int fib(int n) 
{ 
  int f[n+1]; 
  int i; 
  f[0] = 0;   f[1] = 1;  
  for (i = 2; i <= n; i++) 
      f[i] = f[i-1] + f[i-2]; 

  return f[n]; 
}

Comparison

Memotisation Tabular
Top down bottom up
on demand all 
fib(40) tabulated ->  0.000066 sec
fib(40) memotised -> 0.000047
fib(40) naive recursive -> 0.938955
Optimal Substructure

Optimal(problem) == Optimal(Union of subproblems)

Longest Path -> ❎

Shortest path -> ✅