Course contentsShow
← Computer Science
Lesson 912 of 2,87221. Greedy AlgorithmsFree lesson

Greedy vs Dynamic Programming Decision

Develop intuition for recognizing when a problem requires greedy versus dynamic programming approaches.

Greedy vs Dynamic Programming Decision

You'll learn: How to decide whether a problem calls for a greedy algorithm or dynamic programming.

When to Choose Which

You've seen both greedy algorithms (make the locally optimal choice at each step) and dynamic programming (solve overlapping subproblems). But how do you know which approach fits a problem?

Use Greedy when:

  • The greedy choice property holds: making the locally optimal choice always leads to a globally optimal solution
  • There's no need to reconsider past decisions
  • Example: Activity Selection — once you pick the earliest-finishing activity, you never need to "undo" that choice

Use Dynamic Programming when:

  • You need to explore multiple possibilities before deciding
  • Later choices depend on comparing different earlier scenarios
  • The greedy approach produces counterexamples (suboptimal results)
  • Example: 0/1 Knapsack — taking the "best" item first might fill your bag poorly; you need to compare "take it" vs "leave it" for every item

The Litmus Test

Think of it like packing for a trip. Greedy is like grabbing clothes in order of preference until your bag is full — works if items are small and you just want maximum value. Dynamic Programming is like trying different combinations — "what if I skip this bulky jacket to fit three shirts instead?" — necessary when items have complex size/value tradeoffs.

Ask yourself: "If I make what seems like the best choice now, could I later regret it and wish I'd chosen differently?" If yes, you likely need DP. If the locally best choice is always safe, greedy works.

Key Takeaway: Choose greedy when the optimal path is built by always taking the locally best step; choose dynamic programming when you must compare multiple paths through overlapping subproblems to find the global optimum.