<p>The main difference, in my view, is that DP solves subproblems optimally, then makes the optimal current decision given those sub-solutions. Greedy makes the "optimal" current decision given a local or immediate measure of what's best.</p>

<p>Greedy doesn't reason about the subsequent choices to be made, so its measure of what's best is shortsighted and might be wrong. For example, a greedy pathfinding algorithm might always advance directly toward the target, since at each step this decreases the distance left to be traveled the most. But then it might run into a barrier and have to travel all the way around, resulting in a bad solution.</p>

CC BY-SA 3.0
2016-02-28T13:38:37.100Z
Nice comparison. When making the current decision, DP aims to finally arrive to an global optimal solution while GA (greedy algorithms) does not consider the potential impact on subsequent decisions. However, depending on the problems, the two ideologies may coincide as for the Dijkstra's algorithm. 
Let's see if there will be more answers.
Leo
CC BY-SA 3.0
2016-02-28T14:43:36.543Z
@Leo I would not consider Djikstra's algorithm an instance of a greedy algorithm. Another feature of greedy is that it makes an immediate irrevocable choice at the current step. Djikstra's is willing to update or throw away past decisions when it finds better ones.
usul
CC BY-SA 3.0
2016-02-29T10:01:49.447Z
It's true that if i'm asked to provide a greedy algorithm for the sortest path problem, I'll not give Dijkstra's algorithm! :-D
It may be interesting to read Sniedovich 2006, since he stated that Dijkstra's has been generally considered as a greedy algorithm.
Leo
CC BY-SA 3.0
2016-02-29T14:07:05.457Z
@Leo, it's interesting, but I don't see great support for that label. It does have a greedy component in the choice of which node to explore next (this is referenced as the greedy part of Dijkstra's in the paper), but I would argue it is not greedy in how it chooses its solution.
usul
CC BY-SA 3.0
2016-03-07T08:45:01.990Z
perhaps you are right, Dijkstra's is not SO greedy especially when the current decision is somehow based on previous ones!
Leo
CC BY-SA 3.0
2016-02-27T23:43:48.383Z
2016-02-27T23:43:48.383Z
usul
<p>Dynamic programming is not a greedy algorithm. It just embodies notions of recursive optimality (Bellman's quote in your question).</p>

<p>A DP solution to an optimization problem gives an optimal solution whereas a greedy solution might not.</p>

CC BY-SA 3.0
2016-02-27T21:40:13.087Z
Thanks for the reply. If we read carefully the optimality principle of dp, there is obviously a greedy thinking there no? Consider the bottom-up setting of dp, at each level we are trying to construct a larger solution to the best (so greedy), and at that point dp is rather a greedy algo to the optimality.
Leo
CC BY-SA 3.0
2016-03-04T04:18:55.623Z
@Leo. I don't think so. Let's take the example of a DP with n stages. Then DP (n) = min (DP(n-1,t), c(n-1,n,t)) where c(n-1,n, t) is the cost of going from stage n-1  to n via option t. So we are looking at not only stage n-1 but also the stages before it indirectly  through DP(n-1,t). In this sense I think it's not greedy
wabbit
CC BY-SA 3.0
2016-03-07T08:41:29.567Z
Thanks @Wabbit for the explanation, it's now clearer for me on the difference between the two. A decision in DP is always based on the information of previous decisions while GA only makes decisions based on its local view!
Leo
CC BY-SA 3.0
2016-02-27T17:23:25.540Z
2016-02-27T17:23:25.540Z
wabbit
<p>In (Sniedovich 2006) "<em>Dijkstra's algorithm revisited: the dynamic programming connexion</em>", Sniedovich provides us another interpretation of Dijkstra's algorithm as a dynamic programming implementation. By curiosity, I found the historical book of Bellman 1954: "<em>Dynamic Programming</em>", in which Bellman bases Dynamic Programming on the following <em>Principle of optimality</em> (page 84):</p>

<blockquote>
  <p>An optimal policy has the property that whatever the initial state and initial decision are, the remaining decisions much constitute an optimal policy with regard to the state resulting from the first decision.</p>
</blockquote>

<p>This is the core of dynamic programming while my feeling is that it's exactly the same as the "Principle of Greed". </p>

<p>So the question is, are DP and Greedy algorithms just two different views of exactly the same thing? Or let's say that they share the same philosophy?
If the answer is no, what are the main differences between them?</p>

<ds.algorithms><dynamic-programming><greedy-algorithms>
Dynamic Programming vs Greedy Algorithm
Leo
# Dynamic Programming vs Greedy Algorithm

(Asked by: username_0 on 2016-02-27)

In (Sniedovich 2006) "*Dijkstra's algorithm revisited: the dynamic programming connexion*", Sniedovich provides us another interpretation of Dijkstra's algorithm as a dynamic programming implementation. By curiosity, I found the historical book of Bellman 1954: "*Dynamic Programming*", in which Bellman bases Dynamic Programming on the following *Principle of optimality* (page 84):

> An optimal policy has the property that whatever the initial state and initial decision are, the remaining decisions much constitute an optimal policy with regard to the state resulting from the first decision.

This is the core of dynamic programming while my feeling is that it's exactly the same as the "Principle of Greed".

So the question is, are DP and Greedy algorithms just two different views of exactly the same thing? Or let's say that they share the same philosophy?
If the answer is no, what are the main differences between them?

**Tags:** ds.algorithms, dynamic-programming, greedy-algorithms

---

## 2 answers

### Answer by username_1 on 2016-02-27. Score: 3 | Accepted answer

The main difference, in my view, is that DP solves subproblems optimally, then makes the optimal current decision given those sub-solutions. Greedy makes the "optimal" current decision given a local or immediate measure of what's best.

Greedy doesn't reason about the subsequent choices to be made, so its measure of what's best is shortsighted and might be wrong. For example, a greedy pathfinding algorithm might always advance directly toward the target, since at each step this decreases the distance left to be traveled the most. But then it might run into a barrier and have to travel all the way around, resulting in a bad solution.

> **Comments:**
> **username_0**: Nice comparison. When making the current decision, DP aims to finally arrive to an global optimal solution while GA (greedy algorithms) does not consider the potential impact on subsequent decisions. However, depending on the problems, the two ideologies may coincide as for the Dijkstra's algorithm.  Let's see if there will be more answers.  
> **username_1**: @Leo I would not consider Djikstra's algorithm an instance of a greedy algorithm. Another feature of greedy is that it makes an immediate irrevocable choice at the current step. Djikstra's is willing to update or throw away past decisions when it finds better ones.  
> **username_0**: It's true that if i'm asked to provide a greedy algorithm for the sortest path problem, I'll not give Dijkstra's algorithm! :-D It may be interesting to read Sniedovich 2006, since he stated that Dijkstra's has been generally considered as a greedy algorithm.  
> **username_1**: @Leo, it's interesting, but I don't see great support for that label. It does have a greedy component in the choice of which node to explore next (this is referenced as the greedy part of Dijkstra's in the paper), but I would argue it is not greedy in how it chooses its solution.  
> **username_0**: perhaps you are right, Dijkstra's is not SO greedy especially when the current decision is somehow based on previous ones!  

---

### Answer by username_2 on 2016-02-27. Score: 2

Dynamic programming is not a greedy algorithm. It just embodies notions of recursive optimality (Bellman's quote in your question).

A DP solution to an optimization problem gives an optimal solution whereas a greedy solution might not.

> **Comments:**
> **username_0**: Thanks for the reply. If we read carefully the optimality principle of dp, there is obviously a greedy thinking there no? Consider the bottom-up setting of dp, at each level we are trying to construct a larger solution to the best (so greedy), and at that point dp is rather a greedy algo to the optimality.  
> **username_2**: @Leo. I don't think so. Let's take the example of a DP with n stages. Then DP (n) = min (DP(n-1,t), c(n-1,n,t)) where c(n-1,n, t) is the cost of going from stage n-1  to n via option t. So we are looking at not only stage n-1 but also the stages before it indirectly  through DP(n-1,t). In this sense I think it's not greedy  
> **username_0**: Thanks @Wabbit for the explanation, it's now clearer for me on the difference between the two. A decision in DP is always based on the information of previous decisions while GA only makes decisions based on its local view!  

---

