01Overview
In the 1950s Bellman introduced dynamic programming while studying multi-stage decisions, characterising a class of decomposable problems by optimal substructure: the global optimum is built from optimal sub-solutions. The key is to eliminate recomputation — store the answers for subproblems in a table.
DP then became a cross-disciplinary method: edit distance and Needleman–Wunsch made biological sequence alignment possible; Viterbi finds the most likely path in a hidden Markov model; knapsack, interval scheduling and matrix-chain multiplication are the standard exercises. The hard part is not writing the recurrence but defining the state — design the state well and half the problem is solved.
02History
- 1953
Bellman introduces dynamic programming
Optimising decisions made in stages.
- 1967
The Viterbi algorithm
The best path through a hidden Markov model.
- 1970
Needleman–Wunsch
Dynamic programming for biological sequence alignment.
- 1970
Knapsack and interval DP systematised
Both enter the algorithms textbooks.
03Core concepts
Optimal substructure
The global optimum contains optimal solutions to subproblems.
State and transition
Describe a subproblem with parameters and write the recurrence between states.
Memoisation
Cache computed subproblems in top-down recursion.
04Hands-on
Do it once — it beats reading it ten times
Implement edit distance and print the full table, not just the answer — then trace back the alignment
05Self-check
Say it in your own words first, then open the answer. Whatever you cannot explain is what to review next.
Can you explain "Optimal substructure"?
The global optimum contains optimal solutions to subproblems.
Can you explain "State and transition"?
Describe a subproblem with parameters and write the recurrence between states.
Can you explain "Memoisation"?
Cache computed subproblems in top-down recursion.
What problem did it solve, and why was there nothing better at the time?
Go back to the history section: how was this done before, and what did it cost?
If you had to build it today, how would you break it down?
Use the hands-on task above: write a plan of at most three steps before you start.
06Key people
Richard Bellman
1920 – 1984
Dynamic programming and the Bellman equation.
Andrew Viterbi
1935 –
The Viterbi algorithm and CDMA.
07Further reading
- Dynamic Programming and Optimal Control
- Introduction to Algorithms, Chapter 15