Computer Science‎ > ‎

Dynamic Programming

A method for solving complex problems by breaking them up into sub-problems first. This technique can be used when a given problem can be split into overlapping sub-problems and when there is an optimal sub-structure to the problem. Often used in optimization problems (max,min) - some examples of which are given later. 

(Informally) generally used for problems of the type :  f(x)= Some function of ( f(x-a), f(x-b) ... etc. )  
Simple Example : 


1. Consider the Fibonacci Series : 

0,1,1,2,3,5,8,13,21...

F(0)=0 ; F(1) = 1; F(N)=F(N-1)+F(N-2) 

Pseudo-code for a simple recursive function will be :

fib(int n)
{
    if (n==0) return 0;
    if (n==1) return 1;
    return fib(n-1)+fib(n-2);
}

Using the above function, if we want to compute fib(7), we end up making a tree of calls which computes the function on the same value, several times :
fib(6) = fib(5) + fib(4)
fib(6) = ( fib(4)+fib(3) ) + ( fib(3) + fib(2) )
fib(6) = ( (fib(3) + fib(2)) + ( fib(2) + fib(1)) ) + ( (fib(2) + fib(1)) + (fib(1) + fib(0) )
fib(6) = ( ( ( fib(2) + fib(1) ) +( fib(1) + fib(0) ) ) + ( ( fib(1) + fib(0) ) + fib(1) ) ) + ( ( (fib(1)+fib(0)) + fib(1) ) + ( fib(1) + fib(0) ) )
fib(6) = ( ( ((fib(1)+fib(0)) + fib(1) ) +( fib(1) + fib(0) ) ) + ( ( fib(1) + fib(0) ) + fib(1) ) ) + ( ( (fib(1)+fib(0)) + fib(1) ) + ( fib(1) + fib(0) ) )

As you can see : fib(5) has been computed once.
fib(4) has been computed 2 times.
fib(3) has been computed 3 times.
fib(2) has been computed 5 times.


2. Dynamic Knapsack Problem 



 


ċ
dynamicKnapsack.jar
(5k)
Prashant Bhattacharji,
Aug 2, 2011, 3:05 AM
ċ
fibonacciVisualization.jar
(4k)
Prashant Bhattacharji,
Aug 2, 2011, 3:05 AM
Comments