doubt in Dynamic programming.

Hi sushant,

Both in the DP and DC, we will moduralise the problem and get the solution. There is a small minor difference is there actually.
In DP, Reusability is the main thing in which some part of the solution is obtained; that is the beauty of DP. In the sence, we use some already calculated values to solve our problem and no need to calculate them again and again. And here there is a recurrance formula which deals overlapping problems. you have to visualise all the loops in CP.

A good example for DP is 0/1 knapsack problem.

Principle of Optimality is the major rule, have to follow in DP. It states that, an optimal sequence of decisions has the property that,
whatever the initial state and decision are, the remaining decisions must constitute an optimal decision sequence, with regard to, the state resulting from the first decision.

Merge sort is a good example for DC. We cant solve overlapping problem using DC, thats why we opt for DP for some problems. And in Dc, the nature of the problem is same but not in DP.

First we have to solve a problem with DC, if we cant get the solution then we will go for DP. Because DP is costliest method. So, mainly there are 2 disadvantages between DP an DC.
1) By using DP, we can solve overlapping problems but not with DC.
2) The nature of the problem is same in DC but not in DP.

Let me know you are clear about this or not. And feel free to ask me any doubts regarding this.
Thanks for asking this question. DAA is a good subject and I like that subject.

we can solve overlapping problems

what are overlapping problems?

goyal420

what are overlapping problems?

What i have studied that a recursive algorithm for the problem solves the same subproblem again and again ,rather than generating the new subproblems.So, when a recursive algorithm revisit again and again then it is said that the optimization problem has overlapping subproblems.
For which divide and conquer algorithm generate new subproblem at each step of recursion.
So, this is the disadvantage of Divide and conquer algorith over the Dynamic programming.

Hi Sahithi pallavi,

Thank you.
I have cleared most of my doubts but still have some doubts.
We know that dynamic programming is applicable to those problem that posses two properties ;-
1) Optimal substructure property.
2) Overlapping Subproblems property.

please make me clear about what is Optimal substructure.

Now i cleared about optimal substructure that ,a problem exhibit the optimal substructure property if and only if an optimal sloution to the problem contains within it the optimal solution of the subproblem.

We know that Dynamic programming uses optimal substructure in a botton -up fashion.
Then please explain what is botton -up fashion.

what is botton -up fashion.

Starting from solution of sub problems ---------------------------> to reach solution of main problems

This is main idea behind Dynamic programming ie you use all the solutions in order to reach solution of main problem

As Name indicate
solution of
Main problem ^
| |
| |
| |
| |
solution of Sub problems

I hope you will get an idea regarding this Bottom up design

@ Goyal

I have understood that what is bottom-up fashion in Dynamic Programming but can you please give a simple example of buttom - up fashion so i have better idea of dynamic programming algorithm.
And
What is the practical application of Dynamic Programming?

you can take make a change problem ie i have 8 rs and coins of 1,4,3 rs
I want to give someone minimum no of coins in order return 8 rs
If i follow greedy approach(just for comparasion)
then i will give him 1 -4rs coin and 1-3rs coin and 1-1rs coin
which is obviously not a optimal solution since we can give him 2-4rs coins also so we will follow dynamic programming approach

Here we find all the possible solution in then use these to find the main solution

I have made a program ,Just try to understand its algorithm you will get to know what i am trying to explain

    [FONT=&quot]#include<iostream.h>[/FONT]
  [FONT=&quot]#include<conio.h>[/FONT]
  [FONT=&quot]#define infinite 100000[/FONT]
  [FONT=&quot]int check(int store[],int d[],int,int);[/FONT]
  [FONT=&quot]int min(int,int);[/FONT]
  [FONT=&quot]void main()[/FONT]
  [FONT=&quot]{[/FONT]
  [FONT=&quot]int last,key,*a[3],d[3],i,amount,j,no,dk,*store,amt,amp;[/FONT]
  [FONT=&quot]cout<<"Enter amount"<<endl;[/FONT]
  [FONT=&quot]cin>>amount;[/FONT]
  [FONT=&quot]amt=amount;[/FONT]
  [FONT=&quot]amp=amount;[/FONT]
  [FONT=&quot]for(i=0;i<3;i++)[/FONT]
  [FONT=&quot]{[/FONT]
  [FONT=&quot]a[i]=new int[amount+1];[/FONT]
  [FONT=&quot]}[/FONT]
  [FONT=&quot]cout<<"Please enter the type of coins available in increasing order"<<endl;[/FONT]
  [FONT=&quot]for(i=0;i<3;i++)[/FONT]
  [FONT=&quot]{[/FONT]
  [FONT=&quot]cin>>d[i];[/FONT]
  [FONT=&quot]}[/FONT]
  [FONT=&quot]for(i=0;i<3;i++)[/FONT]
  [FONT=&quot]{[/FONT]
  [FONT=&quot]    for(j=0;j<=amount;j++)[/FONT]
  [FONT=&quot]    {[/FONT]
  [FONT=&quot]    a[i][0]=0;[/FONT]
  [FONT=&quot]         if(i==0&j<d[i])[/FONT]
  [FONT=&quot]         {[/FONT]
  [FONT=&quot]             a[i][j]=infinite;[/FONT]
  [FONT=&quot]         }[/FONT]
  [FONT=&quot]         else[/FONT]
  [FONT=&quot]             if(i==0)[/FONT]
  [FONT=&quot]             {[/FONT]
  [FONT=&quot]             a[i][j]=1+a[i][j-d[i]];[/FONT]
  [FONT=&quot]             }[/FONT]
  [FONT=&quot]             else[/FONT]
  [FONT=&quot]         {[/FONT]
  [FONT=&quot]             if(j<d[i])[/FONT]
  [FONT=&quot]             {[/FONT]
  [FONT=&quot]             a[i][j]=a[i-1][j];[/FONT]
  [FONT=&quot]             }[/FONT]
  [FONT=&quot]             else[/FONT]
  [FONT=&quot]             {[/FONT]
  [FONT=&quot]             a[i][j]=min(a[i-1][j],1+a[i][j-d[i]]);[/FONT]
  [FONT=&quot]             }[/FONT]
  [FONT=&quot]         }[/FONT]
  [FONT=&quot]         }[/FONT]
  [FONT=&quot]}[/FONT]
  [FONT=&quot]cout<<"Required table is"<<endl;[/FONT]
  [FONT=&quot]for(i=0;i<3;i++)[/FONT]
  [FONT=&quot]{[/FONT]
  [FONT=&quot]cout<<endl;[/FONT]
  [FONT=&quot]for(j=0;j<=amount;j++)[/FONT]
  [FONT=&quot]{[/FONT]
  [FONT=&quot]cout<<a[i][j]<<" ";[/FONT]
  [FONT=&quot]}[/FONT]
  [FONT=&quot]}[/FONT]
  [FONT=&quot]for(i=0;i<3;i++)[/FONT]
  [FONT=&quot]{[/FONT]
  [FONT=&quot]for(j=0;j<=amount;j++)[/FONT]
  [FONT=&quot]{[/FONT]
  [FONT=&quot]if(!(i==2))[/FONT]
  [FONT=&quot]    {[/FONT]
  [FONT=&quot]    if(a[i][amount]>a[i+1][amount])[/FONT]
  [FONT=&quot]    {[/FONT]
  [FONT=&quot]    dk=i+1;[/FONT]
  [FONT=&quot]    }[/FONT]
  [FONT=&quot]    else[/FONT]
  [FONT=&quot]    {[/FONT]
  [FONT=&quot]    dk=i;[/FONT]
  [FONT=&quot]    }[/FONT]
  [FONT=&quot]}[/FONT]
  
  [FONT=&quot]}[/FONT]
  
  [FONT=&quot]}[/FONT]
  [FONT=&quot]cout<<"Value of dk"<<dk<<endl;[/FONT]
  [FONT=&quot]key=dk;[/FONT]
  [FONT=&quot]store=new int[dk+1];[/FONT]
  [FONT=&quot]for(int m=0;m<=dk;m++)[/FONT]
  [FONT=&quot]{[/FONT]
  [FONT=&quot]store[m]=0;[/FONT]
  [FONT=&quot]}[/FONT]
  [FONT=&quot]for(i=dk;i>=0;i--)[/FONT]
  [FONT=&quot]{[/FONT]
  [FONT=&quot]for(j=0;j<=amount;j++)[/FONT]
  [FONT=&quot]{[/FONT]
  
  
  [FONT=&quot]             if(a[i][j]*d[i]>amt)[/FONT]
  [FONT=&quot]             {   [/FONT]
  [FONT=&quot]             store[i]=a[i][j-1];[/FONT]
  [FONT=&quot]             cout<<a[i][j-1]<<" "<<"mine"<<endl;[/FONT]
  [FONT=&quot]             amt=amt-d[i]*store[i];[/FONT]
  [FONT=&quot]             break;[/FONT]
  [FONT=&quot]             }[/FONT]
  [FONT=&quot]             else[/FONT]
  [FONT=&quot]             {[/FONT]
  [FONT=&quot]                 if(a[i][j]*d[i]==amt)[/FONT]
  [FONT=&quot]                 {[/FONT]
  [FONT=&quot]                 store[i]=a[i][j];[/FONT]
  [FONT=&quot]                 cout<<a[i][j]<<" "<<"mine"<<endl;[/FONT]
  [FONT=&quot]                 amt=amt-d[i]*store[i];[/FONT]
  [FONT=&quot]                 break;[/FONT]
  [FONT=&quot]                 }[/FONT]
  [FONT=&quot]             }[/FONT]
  [FONT=&quot]    }[/FONT]
  [FONT=&quot]}[/FONT]
  
  [FONT=&quot]cout<<endl;[/FONT]
  [FONT=&quot]cout<<"coins are"<<endl;[/FONT]
  [FONT=&quot]int chk=check(store,d,amp,dk);[/FONT]
  [FONT=&quot]if(chk==0)[/FONT]
  [FONT=&quot]{[/FONT]
  [FONT=&quot]cout<<"You can't get a change with these coins sorry"<<endl;[/FONT]
  [FONT=&quot]}[/FONT]
  [FONT=&quot]else[/FONT]
  [FONT=&quot]{[/FONT]
  [FONT=&quot]    for(i=0;i<=dk;i++)[/FONT]
  [FONT=&quot]    {[/FONT]
  [FONT=&quot]    cout<<"we want "<<store[i]<<"--"<<d[i]<<"type of coin"<<endl;[/FONT]
  [FONT=&quot]    }[/FONT]
  [FONT=&quot]}[/FONT]
  [FONT=&quot]}[/FONT]
  [FONT=&quot]int min(int a,int b)[/FONT]
  [FONT=&quot]{[/FONT]
  [FONT=&quot]    if(a>b)[/FONT]
  [FONT=&quot]    {[/FONT]
  [FONT=&quot]         return b;[/FONT]
  [FONT=&quot]    }[/FONT]
  [FONT=&quot]    else[/FONT]
  [FONT=&quot]    {[/FONT]
  [FONT=&quot]         return a;[/FONT]
  [FONT=&quot]    }[/FONT]
  [FONT=&quot]}[/FONT]
  
  [FONT=&quot]int check(int store[],int d[],int amount,int dk)[/FONT]
  [FONT=&quot]{[/FONT]
  [FONT=&quot]int i,sum=0;[/FONT]
  [FONT=&quot]for(i=0;i<=dk;i++)[/FONT]
  [FONT=&quot]{[/FONT]
  [FONT=&quot]sum=sum+store[i]*d[i];[/FONT]
  [FONT=&quot]}[/FONT]
  [FONT=&quot]if(sum==amount)[/FONT]
  [FONT=&quot]{[/FONT]
  [FONT=&quot]return 1;[/FONT]
  [FONT=&quot]}[/FONT]
  [FONT=&quot]else[/FONT]
  [FONT=&quot]{[/FONT]
  [FONT=&quot]return 0;[/FONT]
  [FONT=&quot]}[/FONT]
  

You can also follow Introduction to algorithm by cormen .it is best

Sorry i have made 3 posts by mistake please delete it

Nice example goyal to explain DP! Hope sushant will clear all his doubts if he get this.

hi friends,
I have some doubts.
1.when "DP is based on botom up design" it means assosiation of subproblems but firstly we have to devide them i unable to understand that how this can be done?
2."DP find the optimal solution from set os solutions" but i want to know that in DP we have to find all the solutions and then chose for optimal solution?
3."in DP does not take place any repetition" then how we calculate the solution in just once execution?

@Goyal
Thank you goyal that example was nice .

you mean to say that in case of greedy approach, we have to make the choice which looks best at the time.
Greedy algorithm doesnot look for the global problem as in the case of Dynamic programming.
am i right.

Yes ,Greedy approach choose best .It Provides optimal solution in some cases not all

@Mohit
The answer to first question is in my program .Just try to understand it you will get to know How DP works?

2:-Yes .We find solution for all sub problems as in my previous example we first find solution for 1rs,2rs,3rs,4rs,5rs ........
then use all to reach solution of required problem

3:-I don't understand what you mean?Can you elaborate it more?

@ Goyal

It means that greedy approach doesnot guarantee the optimal solution.

.
1.when "DP is based on botom up design" it means assosiation of subproblems but firstly we have to devide them i unable to understand that how this can be done?

Dynamc programming is like divide and conquer algorithm.
In case of divide and conquer solve the each
subproblem individually and recursively but here the subproblems are independent but in case of DP the subproblems are not independent, that means subproblems share subsubproblems.

DP is buttom-up design. Here, first we have to solve the each suproblem and choose the solutions with the minimum cost called as optimal solution.
But in casse of Greedy Algorithm(just for comparison) we make the choice which looks best at the time and then solve the resulting subproblem.It means that greedy Algorithm doesnot give always the optimal solution.
greedy Algorithm is top-down design and

sushant005

It means that greedy approach doesnot guarantee the optimal solution.

Yes exactly! The name itself indicates that the method should be greedy. So, its just a try to get an optimal solution. If we get the solution, it will be the best. Otherwise, we will opt for another method. So, It doesn't guarantee the optimal solution.

Knapsack problem is the best example for Greedy method to get optimal solution!

In case of divide and conquer solve the each
subproblem individually and recursively but here the subproblems are independent but in case of DP the subproblems are not independent, that means subproblems share subsubproblems.

Bingo very right 😀

mohit007kumar00

3."in DP does not take place any repetition" then how we calculate the solution in just once execution?

The DP supports the memoization concept.
According to this concept when the subproblem is first encountered during the execution of the recursive algorithm,its solution is being stored in the table and it returns the value whenever the subproblem is encountered.

@goyal

In dynamic programming we have to calculate all the solution of a particular problem.
then i think that dynamic programming is slowest among all the tech of algorithm.
but after first execution it stores the data of every execution.
so i think it,s not slower when we execute it for 2nd time.
correct me if i am wrong.
.
can you give me any example of dynamic programming(i want to know where it is used like dc is used to find the run time of merg sort).
.
😁

In dynamic programming we have to calculate all the solution of a particular problem.
then i think that dynamic programming is slowest among all the tech of algorithm.
but after first execution it stores the data of every execution.
so i think it,s not slower when we execute it for 2nd time.

Yes you can say but here in programming if you consider algorithms you should not consider the execution time of sub problem

You should consider whole execution time of program and for that case DP approach is quite nice but if i consider travelling salesman

person problem then yes dp will not be suitable at that case as for some increase in input size there will be huge increase in execution time.


I have already explained a example .Read my previous posts


Note :-I think you are facing many difficulties in these .So it would be better if you follow some book like cormen
It would help you a lot

@goyal

more than 100 brain,s work here.
and on the book only one and that,s me.
so the question,s like my last post does,nt get answered by any particular book.
that,s why we are here to discuss those minor things.

thank for your reply goyal!!
net i get cleared about DP up to some extent.
.

I am replying on a very old post though. but would like to answer what mohit has asked. We generally use DP for problems which dont have a polynomial time algorithms. TSP, Knapsack are examples where you will use DP 'and' compared to such problem's (NP in particular) exponential time algorithms, DP gives a faster approach. If you want to check how efficient DP is, write a recursive program to calculate Fibonacci and write improved DP approach to calculate the same. since in Fibonacci calculation, overlapping subproblems are huge.. it reduces number of calls to 'great great' extent. you can practically see it by keeping track of number of calls in both approaches and print it 😀