How can we say that every greedy problem can be solved using do?
Every greedy can be solved using DP
@Avi-Kasliwal-315786729062203 Greedy approach: Choose whatever you think is optimal now, assuming it will be optimal in the long run.
For example when you are driving and see traffic jam on one road you may take an alternate road which looks empty. This may work but the alternate road can have more severe traffic jam around the corner.
Dynamic Programming on the other hand uses memory to store calculations/results that you have done previously to save time the next time you need them. Using above problem again, The DP Solution would be to calculate traffic on every road and then choose the road(s) which gives best (optimal) time.
In this sense DP is more like a Divide and Conquer approach but with memory. You do not calculate results of sub problems again and again.
And to answer your question
is it safe to say that dp can solve all the problems that can be solved by greedy
I think it is safe to say dp can solve all the problems divide and conquer can solve (may take more memory though)
Of all the examples I can think of DP can give optimal solutions for questions that can be solved optimally by greedy (DP may take exponential time though and almost in each case DP will take more memory).
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.