Step by Step
D
Divide — break the problem into overlapping subproblems
Dynamic programming works by breaking a complex problem down into smaller, overlapping subproblems, where the same subproblem tends to recur multiple times within the larger computation.
Example: computing Fibonacci numbers recursively naturally involves recomputing the same smaller Fibonacci values repeatedly unless those results are stored.
S
Store — memoization or tabulation
Rather than recomputing the same subproblem repeatedly, DP stores each subproblem's solution once it's computed. This can be done top-down (memoization — recursive with caching) or bottom-up (tabulation — iterative, building up from the smallest subproblems first).
Example: storing Fibonacci(10) once it's calculated, so it never needs to be recalculated again during the rest of the computation.
R
Reuse — never solve the same subproblem twice
Whenever the same subproblem is encountered again, the stored result is reused directly instead of being recomputed, which is what gives DP its dramatic efficiency advantage over naive recursive approaches.
Example: the Viterbi algorithm reuses previously computed probabilities for earlier positions in a sequence rather than recalculating them for every possible path through a Hidden Markov Model.
Applied Walkthrough
1
A speech recognition system needs to determine the most likely sequence of words given a noisy audio signal, modeled as a Hidden Markov Model.
2
Checking every possible sequence of hidden states exhaustively would be computationally infeasible for any realistic sentence length.
3
The Viterbi algorithm instead uses dynamic programming, storing the best (highest probability) path to each state at each position, and reusing those stored results to efficiently build up the overall most likely sequence.
4
This same DP approach is also used for part-of-speech (POS) tagging, where the goal is similarly to find the most likely sequence of grammatical tags given a sentence.
Exam Application
Exams test whether you can identify the two required conditions for using dynamic programming — optimal substructure (the optimal solution can be built from optimal solutions to subproblems) and overlapping subproblems (the same subproblems recur multiple times) — and whether you know Viterbi as the specific DP algorithm used for HMM-based sequence problems like speech recognition and POS tagging.
⚠ Common Trap
The most common trap is applying DP to a problem that only has optimal substructure but NOT overlapping subproblems (in which case a simpler divide-and-conquer approach without memoization would be sufficient), or vice versa — both conditions need to hold for DP to provide its characteristic efficiency benefit.
✓ Quick Self-Check
1. What are the two required conditions for a problem to benefit from dynamic programming?
Optimal substructure and overlapping subproblems.
Tap to reveal / hide
2. What is the difference between top-down (memoization) and bottom-up (tabulation) DP approaches?
Top-down is recursive with caching of results; bottom-up is iterative, building up from the smallest subproblems first.
Tap to reveal / hide
3. What does the Viterbi algorithm use dynamic programming to find?
The most likely sequence of hidden states in a Hidden Markov Model.
Tap to reveal / hide
4. Name two real-world applications of the Viterbi algorithm.
Speech recognition and part-of-speech (POS) tagging.
Tap to reveal / hide
5. Why does storing subproblem solutions make DP more efficient than naive recursion?
Because it avoids recomputing the same subproblem multiple times, which would otherwise happen repeatedly in problems with overlapping subproblems.
Tap to reveal / hide