0
$\begingroup$

Can every problem with a greedy solution be solved using dynamic programming? Why or why not?

I'm not completely sure how to formally reason about this, my understanding about the structure of problems with a greedy/dp solution is quite handwavy.

I found conflicting answers for this online, so I'm not sure what to trust.

$\endgroup$
4

1 Answer 1

0
$\begingroup$

Both greedy and dynamic programming are algorithm design techniques, typically used to solve optimization problems. The same problem can be solved in multiple ways using various techniques, including plain old brute-force. The real question to ask is whether using one technique over the other can lead to a more efficient solution or not.

There are two concepts, namely: optimal substructure

a problem is said to have optimal substructure if an optimal solution can be constructed from optimal solutions of its subproblems.

Typically, a greedy algorithm is used to solve a problem with optimal substructure if it can be proven by induction that this is optimal at each step.

and overlapping subproblems

a problem is said to have overlapping subproblems if the problem can be broken down into subproblems which are reused several times

In order to make 'efficient' use of dynamic programming, your problem must exhibit both of these properties. Typically, dynamic programs take substantial space and/or time to obtain an optimal solution from their greedy counterpart, making the greedy solution more lucrative (at least in most cases). If you already have a greedy selection strategy, it might be pointless to explore multiple subproblems, as in the case of a dynamic program.

$\endgroup$
1
  • $\begingroup$ "The real question to ask is whether using one technique over the other can lead to a more efficient solution or not" but that's not my question. $\endgroup$ Mar 29 at 21:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.