Two strategies for optimization
Many optimization problems break into overlapping or nested choices. Greedy algorithms and dynamic programming both exploit this structure, but they commit to choices very differently.
How greedy works
A greedy algorithm makes the locally best choice at each step and never looks back.
- It is fast and simple because it explores a single path.
- It only finds the global optimum when the problem has the greedy choice property, meaning a local optimum leads to a global one.
- When that property fails, greedy can return a confidently wrong answer.
How dynamic programming works
Dynamic programming considers all relevant subproblems and combines their optimal answers.
- It requires optimal substructure, where an optimal solution is built from optimal subsolutions.
- It exploits overlapping subproblems by storing results so each is solved once.
- It is more expensive than greedy but correct on a much wider range of problems.
Choosing between them
Prove the greedy choice property before trusting greedy. If you cannot, fall back to dynamic programming, which reconsiders combinations rather than committing blindly.
Key idea
Greedy commits to the locally best move and only succeeds when the greedy choice property holds, while dynamic programming weighs many subproblem combinations and is correct more broadly at higher cost.