6,295 views
1 votes
1 votes

Unlike greedy algorithms, dynamic programming method always provide correct/optimal solution.

Is the above statement correct?

1 Answer

0 votes
0 votes
If we compare greedy paradigm with dynamic programming we will see that the former first makes a choice and on the basis of that choice we move forward based on our assumption that the choice which we had made in the first position was correct. Where as in the case of Dynamic Programming first the computations are made and then we make a choice based on our "computations".

Coming to the statement:"Unlike greedy algorithms, dynamic programming method always provide correct/optimal solution.", if we consider the case of a multistage graph problem the answer which we get by the greedy approach is not always the correct answer, but dynamic programming efficiently solves this problem using memoization technique.

If by optimal solution we mean that the solution provided to us is correct then the given statement is correct.

Related questions

4 votes
4 votes
3 answers
3
Lakshman Bhaiya asked Nov 10, 2018
12,277 views
If job $J=(J_{1},J_{2},J_{3},J_{4})$ are given their processing time $T_{i}=(1,1,2,3)$ and deadline are $D_{i}=(3,4,2,3)$ maximum how many job can be done$?$$A)1$ ...