Introduction to Dynamic Programming

 

What is dynamic programming??

It is an algorithmic paradigm that works by breaking a complex problem into sub-problems and stores the result so as to avoid re-computing it.

Difference from Divide and Conquer:

Divide and conquer is slightly a different technique. In that, we divide the problem in to non-overlapping sub-problems and solve them independently, like in merge sort and quick sort.

When to use DP??

•       If the given problem can be broken up in to smaller sub-problems and these smaller sub-problems can in turn be divided in to still-smaller ones, and if in this process, you observe some over-lapping sub-problems, then its a big hint for using Dynamic Programming.

Two Types

•       Overlapping Sub-problems

•       Optimal Sub-structure

Overlapping Sub-problems

•       Some recursive programs involve solving a problem again and again.

•       Instead of solving them again and again we store the results.

Staircase Problem/Fibonacci series

•       How many ways are there to climb n steps if you can take 1 or 2 steps at a time??

Solution:

Memoization- Top Down

/* Memoized version for nth Fibonacci number */
#include<stdio.h>
#define NIL -1
#define MAX 100
int table[MAX];
 
/* Function to initialize NIL values in lookup table */
void  initialize()
{
int i;
for(i = 0; i < MAX; i++)
     table [i] = NIL;
}
 
/* function for nth Fibonacci number */
int fib(int n)
{
if(table [n] == NIL)
{
if( n <= 1 )
table[n] = n;
else
table [n] = fib(n-1) + fib(n-2);
}
return table[n];
}
 
int main ()
{
int n = 10;
initialize();
printf("Fibonacci number is %d ", fib(n));
return 0;
}
Tabulation – Bottom Up
 
/* Function to demonstrate Tabulation */
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];
}
 

Optimal Sub-structure

A problem has Optimal Substructure Property if optimal solution of the given problem can be obtained by using optimal solutions of its subproblems.

For Example:

Consider the problem of finding shortest path between a source and destination node. This problem has following optimal substructure property:

If a node x lies in the shortest path from a source node u to destination node v then the shortest path from u to v is combination of shortest path from u to x and shortest path from x to v.

The All Pair Shortest Path algorithms like Floyd–Warshall and Bellman–Ford are typical examples of Dynamic Programming.

 

Go to top