Dynamic Programming

A powerful algorithmic technique for solving optimization problems by breaking them into overlapping subproblems and storing solutions to avoid redundant computation. The key insight is identifying optimal substructure (optimal solutions contain optimal solutions to subproblems) and formulating recurrence relations that capture the problem’s structure.

Introductory to Advanced

• Basic concepts (edit distance, knapsack): Introductory to Intermediate
• Problem formulation and design: Intermediate
• Advanced applications (sequence alignment, optimal BSTs): Intermediate to Advanced
• Research-level DP (parameterized complexity): Advanced

The technique that revolutionized biology: Dynamic programming isn’t just about optimization—it’s about seeing the structure hidden in complex problems. The mental model of breaking problems into overlapping subproblems applies to:

• Software engineering (memoization, caching strategies)
• Operations research (supply chain optimization, inventory management)
• Decision-making under uncertainty (financial planning, resource allocation)

War Story 1 - The Human Genome Project: The Needleman-Wunsch algorithm (1970) uses dynamic programming to align DNA sequences—finding the optimal way to match two genetic sequences by allowing insertions, deletions, and substitutions. This single algorithm:

• Enabled the Human Genome Project (completed 2003)
• Powers BLAST, used billions of times for sequence database searches
• Drives modern drug discovery by identifying protein similarities
• Earned its creators recognition for transforming computational biology

Without DP-based sequence alignment, modern genomics wouldn’t exist. The algorithm compares 3 billion base pairs in the human genome efficiently enough to be practical.

War Story 2 - Saving Money at Scale: Amazon and UPS save hundreds of millions of dollars annually using DP-based optimization for:

• Package routing and delivery scheduling
• Warehouse inventory placement
• Resource allocation in cloud computing (AWS spot pricing)

The knapsack problem—seemingly academic—directly models these real-world optimization challenges.

1. Edit Distance (Levenshtein) - Minimum edits to transform one string into another
2. Longest Common Subsequence (LCS) - Finding common patterns in sequences
3. 0/1 Knapsack - Optimal selection with weight constraints
4. Subset Sum - Determining if a subset sums to target value
5. Bellman-Ford Shortest Paths - Single-source shortest paths allowing negative weights

6. Matrix Chain Multiplication - Optimal parenthesization of matrix products
7. Needleman-Wunsch / Smith-Waterman - Global and local sequence alignment
8. Optimal Binary Search Trees - Minimizing expected search cost
9. Floyd-Warshall - All-pairs shortest paths in O(n³)
10. Chain Matrix Multiplication - Minimizing scalar multiplications

11. Viterbi Algorithm - Most likely sequence in Hidden Markov Models
12. DP on Trees - Tree decomposition and bounded treewidth problems
13. Bitmasking DP - Traveling Salesman in O(n²·2ⁿ)
14. DP with Convex Hull Optimization - Advanced speedup techniques

• Required:

  • Understanding of recursion and recurrence relations
  • Proof by induction
  • Big-O notation and asymptotic analysis
  • Basic combinatorics

• Helpful:

  • Previous exposure to greedy algorithms (for contrast)
  • Graph theory (for path problems)
  • Probability (for probabilistic DP variants)

Setup: You’re writing an essay and realize you typed “algorithm” as “algoritm” throughout. Your editor can delete, insert, or replace characters—each costs 1 operation. What’s the minimum cost to fix all instances?

Naive approach: Try all possible sequences of edits—exponential explosion.

Discovery path:

• “If I knew how to fix ‘algorit’ → ‘algorithm’, could I use that?”
• “What if I process one character at a time from each string?”
• Build a table showing best cost for each prefix pair

The insight: If we know the optimal solution for smaller prefixes, we can build up to the full solution. Three cases at each step:

• Delete from source: 1 + DP[i-1][j]
• Insert into source: 1 + DP[i][j-1]
• Replace (or match): cost + DP[i-1][j-1]

The revelation: The 2D table naturally emerges. Computing bottom-up avoids recomputation. Time: O(mn) vs. exponential naive approach.

Generalization: This pattern—optimal solution depends on optimal subsolutions—is the essence of dynamic programming. The overlapping subproblems are what make DP superior to divide-and-conquer.

Setup: You break into a house with a knapsack that holds 50 kg. Items have weights and values:

• Laptop (3 kg, $2000)
• TV (20 kg, $3000)
• Jewelry (1 kg, $4000)
• …and 50 more items

Which items maximize value without exceeding capacity?

Naive approach: Try all 2⁵³ subsets—infeasible even for computers.

Guided discovery:

• “For the first 10 items and 30 kg capacity, what’s optimal?”
• “If I know the answer for items 1-9, can I decide about item 10?”
• Two choices for each item: take it (if it fits) or leave it

The recurrence emerges:

DP[i][w] = max(
    DP[i-1][w],              // don't take item i
    DP[i-1][w-weight[i]] + value[i]  // take item i (if fits)
)

The insight: A 2D table where DP[i][w] = max value using first i items with capacity w. Build row by row, each cell uses previous row. O(nW) time—pseudo-polynomial but practical for real instances.

Real-world connection: Amazon warehouse optimization uses variants of this for deciding what items to stock where. Saving even 1% in shipping costs = tens of millions of dollars.

Setup: You have two DNA sequences. One is from a crime scene, one from a suspect. But DNA degrades—bases might be missing or corrupted. How do you determine if they match?

The challenge: Simple string matching fails because sequences might have:

• Deletions (missing bases)
• Insertions (extra bases)
• Mutations (substituted bases)

The discovery: Use edit distance, but with biologically meaningful costs:

• Match: 0 cost (bases agree)
• Mismatch: different cost depending on base pair (transition vs. transversion)
• Gap: penalty for insertion/deletion

Why this matters: This is exactly Needleman-Wunsch alignment. Used millions of times daily to:

• Compare patient genomes to reference sequences
• Identify genetic disease markers
• Trace evolutionary relationships
• Design vaccines (comparing virus variants)

The scale: Aligning two sequences of length n takes O(n²) time and O(n²) space. For the human genome (3 billion bases), clever optimizations reduce space to O(n) while keeping O(n²) time—still tractable.

Breaking decisions into stages: Humans often face sequential decision problems: career planning, investment strategies, choosing what to study. Dynamic programming formalizes the principle:

Optimal decisions depend on optimal subdecisions

Backward induction: DP naturally leads to backward reasoning: “If I’m at the last stage, what’s optimal? Now second-to-last?” This mirrors how humans actually plan—working backwards from goals.

The exploration-exploitation tradeoff: Multi-armed bandit problems (a DP application) model the classic dilemma: keep doing what works (exploit) or try new things (explore)? Restaurant choice, career moves, relationships all exhibit this structure.

• Kleinberg & Tardos §6 - Problem-motivated presentation with compelling applications
• Skiena §10 - War stories approach: when to use DP, when it fails
• Erickson Chapter 3 - “Recursion + Memoization = DP”, excellent intuition building
• DPV (Dasgupta-Papadimitriou-Vazirani) §6 - Concise, elegant treatment
• CLRS Ch 15 - Comprehensive reference with detailed analysis

• Compeau & Pevzner “Bioinformatics Algorithms” - Interactive textbook with biological applications
• Jeff Erickson’s notes (http://algorithms.wtf) - Emphasis on problem-solving process
• TopCoder/Codeforces tutorials - Practical competitive programming perspectives

• MIT 6.006 (Demaine/Devadas) - Classic DP lectures available on OCW
• Stanford CS161 - Roughgarden’s derivation-based approach
• CMU 15-451 - Advanced treatment with oral presentations

• Bellman’s original 1954 paper introducing the term “dynamic programming”
• Waterman & Smith (1981) - Local sequence alignment
• PRAM algorithms for parallel DP (research frontier)

• Divide-and-Conquer: DP = divide-and-conquer + overlapping subproblems + memoization
• Greedy Algorithms: When greedy works, it’s often faster than DP; DP handles when greedy fails
• Graph Algorithms: Shortest paths (Bellman-Ford, Floyd-Warshall) are DP on graphs
• Approximation Algorithms: DP provides exact solutions; can be adapted to FPTAS (Fully Polynomial Time Approximation Schemes)
• Parameterized Complexity: DP is key technique for FPT algorithms (fixed-parameter tractable)
• Machine Learning: Hidden Markov Models use DP (Viterbi algorithm); reinforcement learning uses DP (value iteration)

1. Sequence Alignment Visualizer

   • Implement Needleman-Wunsch and Smith-Waterman from scratch
   • Build interactive visualization showing DP table fill order
   • Compare different scoring matrices (BLOSUM, PAM) on real protein data
   • Measure performance on sequences of varying lengths

2. Optimal Resource Allocation Tool

   • Model real-world knapsack variants: multiple knapsacks, item dependencies
   • Build tool for portfolio optimization or project selection
   • Compare DP solution to greedy heuristics
   • Visualize tradeoff between solution quality and computation time

3. Autocorrect Engine

   • Implement edit distance with configurable costs
   • Build dictionary-based spell checker using DP
   • Optimize for real-time performance (explore space optimizations)
   • Add predictive typing using n-gram models

4. Genomics Pipeline

   • Implement DNA sequence alignment with biological scoring
   • Find conserved regions across multiple species
   • Identify potential gene locations
   • Visualize evolutionary relationships via sequence similarity

5. Game AI Using DP

   • Implement optimal strategy for Nim, Coins, or similar game
   • Use DP to precompute game tree for small instances
   • Build interactive player vs. AI
   • Analyze game complexity as parameters scale

3-5 lectures depending on depth

• 2 lectures: Core concepts (edit distance, LCS, knapsack), problem formulation
• 3 lectures: + Matrix chain multiplication, biological sequence alignment
• 4 lectures: + Optimal BSTs, Floyd-Warshall, advanced techniques
• 5 lectures: + Bitmasking DP, tree DP, optimization tricks (convex hull trick)

1. “DP always means filling a table”

   • False! Top-down memoization is equally valid. Choose based on problem structure.

2. “DP is just recursion with memoization”

   • Partially true but misses the key: identifying optimal substructure and formulating the recurrence is the hard creative part.

3. “DP is always optimal”

   • False! DP finds optimal solutions if the problem has optimal substructure. Some problems don’t (e.g., longest path in general graphs).

4. “Bottom-up is always faster than top-down”

   • False! Top-down only computes needed subproblems; bottom-up might compute unnecessary ones. Trade-offs exist.

5. “DP table size must match problem dimensions”

   • False! Space optimization techniques (sliding window, state reduction) often reduce O(n²) to O(n) or O(1) space.

Traditional (banking model):

“Here’s the definition of dynamic programming. Here’s the recurrence for edit distance. Memorize this formula: DP[i][j] = min(DP[i-1][j]+1, DP[i][j-1]+1, DP[i-1][j-1]+cost). Now apply it to these problems.”

Problem-posing approach:

“You need to compare DNA sequences to find disease markers. Simple matching won’t work because DNA degrades—bases go missing. How would you measure similarity allowing for gaps? What if you built up solutions for shorter sequences? Let’s explore this together… Ah, a table emerges naturally! Now we’ve discovered dynamic programming.”

The difference: Students discover why the technique exists and how to derive solutions, not just how to apply memorized formulas. They learn the design process: recognizing optimal substructure, formulating recurrences, choosing memoization strategy.

Curriculum placement:

• Week 2-4 for graduate courses (after divide-and-conquer, before graphs)
• Week 3-5 for advanced undergraduate

Prerequisites check: Students should be comfortable with:

• Recursion and recurrence relations
• Proof by induction (for correctness arguments)
• Basic graph concepts (for shortest path applications)

Why relatively early: DP is foundational for many subsequent topics (graph algorithms, approximation, parameterized complexity). It’s also one of the most practically useful techniques students will learn.

Pedagogical note: Start with one-dimensional DP (Fibonacci, longest increasing subsequence) before jumping to two-dimensional (edit distance, knapsack). The pattern of “build table, fill in order respecting dependencies” transfers.

Ready for students? ✓ Yes - comprehensive coverage, multiple motivating applications, clear progression from basic to advanced, strong real-world connections.