 # 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;   f = 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 -> ✅