Dynamic Programming | Introduction | ADA

 Dynamic Programming

Let we discuss about dynamic programming.Dynamic programming is an optimisation technique and we know Greedy method is also an optimisation  technique but both follow different strategy for solving the problem.

We know optimisation problem are those which gives either minimum results or maximum results.

In greedy method we define to follow predefine procedure to get optimal result. The  procedure is known to be optimal if we get follow the procedure to get the best result like:

In Kruskal's algorithm  for finding minimum spanning tree always select the minimum cost edge that gives the best result.

In Diskstra's shortest path algorithm always select the shortest path vertices and continuing relaxing the vertices we get a shortest path. So this is pre define procedure.

But in dynamic programming we will try to find out all possible solution then pickup the best solution i.e optimum solution.

This process is difficult and time consuming compare to greedy method . For any problem there may be many solution which are feasible , so we are try to find all solution then pickup the best one.

Mostly dynamic programming problem are used to solve by using recursive formulas. Those who are not use recursion of programming but the formulas are  recursive. But this can also be solved using iteration.

A dynamic programming follow a principles of optimality. Optimality say that the problem is solved by taking sequence of decisions to get a optimal solution.

So we can say that in greedy method decision is taken one time and we will follow that decision. But in dynamic programming in every stage we take a decision.While solving a problem  we can understand the working of dynamic programming .

Let we understand by taking Fibonacci series problem:

Fibonacci series is : 0 , 1 , 1 , 2 , 3 , 5 , 8 , 13 .....

Suppose Function is

 int fibon ( int n)

 {

    if (n<=1)

        return (n);

    else

        return ( fibon (n-2) + fibon (n-1);

 }

Let we trace by using memorisation method it is top down approach. We create tracing tree for this problem for n=5.

 

So if we call this recursive function than it will take more time.

If I ask , Is there is any way to reduce the time let we see from the above tracing tree we seen a same function call many times such as fibon(1),fibon(2) etc.

Why we call same function again and again, can be reduce it yes we can reduce it so that the same function

can not call again.

For that take one global array initially we will fill array with -1.

Now by tracing tree we will fill array how let we see.

fibon(5)=-1 don't know the value

fibon(3)=-1 don't know the value

fibon(1) = return 1 so mark it as in array garray[1]=1 it is completed.

fibon(2)= don't know call function by (fibon(0) ,fibon(1))

fibon(0)=0 update in array garray[0]=0 it is completed

fibon(1)= it is already done which is 1 so we will not call again.

just add fibon(0) + fibon(1) i.e (0+1=1) return it to fibon(2)

so fibon(2)=1 update it in array garray[2]=1

Now do fibon(1) + Fibon(2) i.e (1+1=2) which is return to fibon(3)

fibon(3)=2 update it in array garray[3]=2.

Now come to right side

fibon(4) do we know we don't know

fibon(2) shell we call no the result is already known i.e 1.

so don't call fibon(2),fibon(0) and fibon(1) here.

fibon(3) do we know yes we know the answer don't call again i.e 2.

so don't call all below functions such as fibon(2),fibon(0) and fibon(1) here.

Now add fibon(2) + fibon(3) i.e (1+2=3) so

Now fibon(4)=3 update it in array i.e garray[4]=3

Now add fibon(3) + fibon(4) i.e (2+3=5) so

Now fibon(5)=5 update it in array i.e garray[5]=5

Here if we count the number of calls it is only 6.

So if i have given fibon(n) than n+1 call are there. i.e is O(n)

By using this method we avoiding the same call again.

By the help of array we can identified this  function is already called so we will not call again.

So this is a memorisation method it will reduce the call from 2 power n to n.

We can use this method to solve the problem of dynamic programming but mostly we use iterative method.

So let we understand Iterative method or tabulation method.

Let we see how we solve the same problem by using tabulation method.

Here is Iterative method for solving Fibonacci Series:

 int fibon (int n)

 {

    if ( n<=1)

    {

        return(n);

    }

    A[0]=0  , A[1]=1;

 for(i=2;i<=n;i++)

 {

    A[i]=A[i-2] + A[i-1];

 }

 return (A[n]);

 }

By  tracing the above function we will fill  following values in table of Fibonacci series for number=5

Following problems can be solved by using dynamic programming :

1. 0/1 Knapsack problem.

2. Multistage Graph.

3. Reliability Design.

4. Floyd -Warshall algorithm.

We discuss the above problem in next post keep reading.