Can every greedy problem be solved using dynamic programming?

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.

• Borodin, Nielsen and Rackoff formalized greedy algorithms. Alekhnovich et al. formalized dynamic programming, but their model also captures priority algorithms, which are the formalized greedy algorithms suggested by BNR. Mar 28 at 19:27
• Before you make your question precise, it cannot be answered. Mar 28 at 19:27
• Mar 29 at 19:17
• I'll have to read the last one. The second one doesn't answer the question. The first one is a duplicate but the answer does not answer my question specifically and more importantly, all the claims made by it are very handwavy with little reasoning given. Mar 29 at 21:29

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.

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.

• "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. Mar 29 at 21:31