When does a greedy algorithm work, and when do you need dynamic programming instead?

A greedy algorithm makes the best-looking choice at each step and never revisits it. It’s correct when two things hold:

• Greedy-choice property: some optimal solution starts with the greedy choice.
• Optimal substructure: after that choice, the rest is the same kind of problem, solved by the same rule.

You justify it with an exchange argument: take any optimal solution, swap its first choice for the greedy one, and show it doesn’t get worse. Interval scheduling (keep the meeting that ends earliest) is the classic example.

Greedy fails when an early choice can block a better combination. Coins [1, 3, 4] and amount 6: biggest-first takes 4 + 1 + 1 (3 coins), but 3 + 3 uses 2. 0/1 knapsack fails the same way. Those problems need dynamic programming, which considers every choice and reuses the answers to smaller subproblems.

In practice: state the greedy rule, try two or three tiny counterexamples, and only commit to greedy if you can explain why swapping never helps.