FREE LESSON · Algorithms & data structures · 4 OF 4
Greedy Algorithms vs Dynamic Programming
Algorithm mastery: design from structure — Greedy choices, dynamic programming, and proof
The best algorithm often appears after the state is named correctly.
Greedy algorithms commit to a locally best choice and need an exchange or cut argument proving no optimal solution is lost. Dynamic programming stores solutions to overlapping subproblems; its central act is defining a state that contains exactly the information the future needs. Both are proof-driven design patterns.
Do not start by writing loops. Start by stating the subproblem and why its answer composes.
Dynamic programming is a dependency graph
For edit distance, state (i,j) means the optimal cost to transform the first i source symbols into the first j target symbols. Delete, insert, and match/replace transitions point to smaller states. Once that recurrence and base cases are correct, memoization or tabulation chooses the evaluation order.
A DP table is not the idea; the state meaning and recurrence are the idea.