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
will be :simple recursive functionfib(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 |

Computer Science >