Algorithmsmedium

Greedy vs dynamic programming — what’s the key difference?

Answer

Greedy makes the best local choice at each step and never revisits it; it works only when the problem has the greedy-choice property. DP solves overlapping subproblems and reuses results (memoization/tabulation) to guarantee optimality.

Advanced answer

Deep dive

The key difference is *proof of optimality*.

Greedy:

Choose the best local option now.
Works only when a greedy-choice property holds (local choice can be extended to a global optimum).

DP:

Define states and transitions.
Uses optimal substructure + overlapping subproblems.
Guarantees optimality (given the right state model), often with higher memory/time.

Examples

Greedy works: interval scheduling (earliest finish), Huffman coding.
Greedy fails: 0/1 knapsack, many coin systems.
DP works: knapsack, edit distance, LIS (often optimized).

Common pitfalls

Using greedy “because it seems to work” without a correctness argument.
DP with a state explosion (O(n^2) or worse) without checking constraints.

Answer

Advanced answer

Deep dive

Examples

Common pitfalls

Related questions