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

Greedy vs Dynamic Programming

Compare when to use greedy approach versus DP: irreversible choices versus overlapping subproblems.

Greedy vs Dynamic Programming

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


Both greedy algorithms and dynamic programming (DP) solve optimization problems, but they work in fundamentally different ways. Understanding when to use each approach is crucial for efficient problem-solving.

The Core Difference

Greedy algorithms make a series of irreversible choices. At each step, you pick what looks best right now, never reconsidering that decision. Think of it like packing a suitcase: once you put an item in, you never take it out to reconsider.

Dynamic programming handles problems with overlapping subproblems—where the same smaller problem appears multiple times. DP solves each subproblem once, stores the result, and can revisit or combine these solutions. It's like solving a jigsaw puzzle: you might try different pieces in different spots until you find the optimal fit.

When to Use Greedy

Choose greedy when:

  • The greedy choice property holds: a local optimum leads to a global optimum
  • You never need to undo decisions
  • Each choice is independent of future unknowns

Example: In the activity selection problem (choosing non-overlapping activities), always picking the activity that finishes earliest provably works.

When to Use Dynamic Programming

Choose DP when:

  • You see overlapping subproblems (same calculations repeated)
  • You need to explore multiple possibilities before deciding
  • The problem exhibits optimal substructure but greedy choices don't guarantee optimality

Example: Computing Fibonacci numbers—fib(5) needs fib(4) and fib(3), but fib(4) also needs fib(3). Without DP, you'd recalculate fib(3) wastefully.

The Key Question

Can you commit to each choice immediately, or must you consider all options?

Key Takeaway: Use greedy when local optimal choices guarantee global optimality and decisions are final; use dynamic programming when you must explore overlapping subproblems and combine solutions optimally.