Reference and Selective Reading
You do not need to read the source books front-to-back for this module. Use the concept pages and practice pages first. Open these local chunks only when you need alternate exposition, more worked examples, or deeper exercise volume.
Source Roles
| Source | Role | Why it is here |
|---|---|---|
| Introduction to Algorithms (CLRS) | Primary rigorous source | Cleanest derivations of optimal substructure, memoization vs tabulation, rod cutting, matrix chain, LCS, optimal BST, and the elements of the greedy strategy |
| The Algorithm Design Manual (Skiena) | Primary applied source | Best working prose on Fibonacci caching, edit distance, LIS, partition/subset sum, triangulation, and the limits of DP (TSP) |
| Competitive Programming (Halim) | Problem variety and advanced DP | Richest source for bitmask DP, digit DP, tree DP, DAG DP, and state-compression techniques |
| Algorithms (Sedgewick) | Supporting prose | Alternate DP framing when CLRS/Skiena is opaque |
| Grokking Algorithms (Bhargava) | Friendly re-entry | Use only as a gentle first pass on grid DP and basic DP intuition |
Read Only If Stuck
Cluster 1: DP Foundations
- CLRS: Part IV -- Advanced Design and Analysis Techniques -- Introduction
- CLRS: 14.1 Rod cutting (Part 1)
- CLRS: 14.1 Rod cutting (Part 2)
- CLRS: 14.1 Rod cutting (Part 3)
- CLRS: 14.3 Elements of Dynamic Programming (Part 1)
- CLRS: 14.3 Elements of Dynamic Programming (Part 2)
- CLRS: 14.3 Elements of Dynamic Programming (Part 3)
- Skiena: 8.1.1 Fibonacci Numbers by Recursion
- Skiena: 8.1.2 Fibonacci Numbers by Caching
- Grokking Algorithms: 9 Dynamic Programming (Part 1)
Cluster 2: Linear and Sequence DP
- Skiena: 8.2 Approximate String Matching
- Skiena: 8.2.2 Edit Distance by Dynamic Programming
- Skiena: 8.2.3 Reconstructing the Path
- Skiena: 8.2.4 Varieties of Edit Distance
- Skiena: 8.3 Longest Increasing Sequence
- Skiena: 8.5 The Partition Problem
- Skiena: 13.10 Knapsack Problem
- CLRS: 14.4 Longest Common Subsequence (Part 1)
- CLRS: 14.4 Longest Common Subsequence (Part 2)
- CLRS: 14.4 Longest Common Subsequence (Part 3)
- Competitive Programming: 3.5 Dynamic Programming
- Competitive Programming: 3.5.2 Classical Examples (LIS)
- Competitive Programming: 3.5.2 Classical Examples (Knapsack)
- Competitive Programming: 3.5.2 Classical Examples (Coin Change)
Cluster 3: Grid, Interval, and Tree DP
- CLRS: 14.2 Matrix Chain Multiplication (Part 1)
- CLRS: 14.2 Matrix Chain Multiplication (Part 2)
- CLRS: 14.2 Matrix Chain Multiplication (Part 3)
- CLRS: 14.5 Optimal Binary Search Trees (Part 1)
- CLRS: 14.5 Optimal Binary Search Trees (Part 2)
- Skiena: 8.6 Parsing Context-Free Grammars
- Skiena: 8.6.1 Minimum Weight Triangulation
- Competitive Programming: 9.20 Matrix Chain Multiplication
- Competitive Programming: 9.22 Max Weighted Independent Set
- Competitive Programming: 3.5.2 Classical Examples (Counting Paths)
- Grokking Algorithms: 9 Dynamic Programming (Part 2)
Cluster 4: Bitmask and Digit DP
- Skiena: 8.7 Limitations of Dynamic Programming (TSP)
- Competitive Programming: 8.3 More Advanced DP Techniques
- Competitive Programming: 8.3.2 Compilation of Common DP Parameters
- Competitive Programming: 8.3.4 MLE: Consider Using Balanced BST as Memo Table
- Competitive Programming: 3.5.3 Non-classical Examples
- Competitive Programming: 6.5 String Processing With DP
Cluster 5: Greedy vs DP and Optimization Tradeoffs
- CLRS: 15.1 Activity-Selection Problem (Part 1)
- CLRS: 15.1 Activity-Selection Problem (Part 2)
- CLRS: 15.2 Elements of the Greedy Strategy (Part 1)
- CLRS: 15.2 Elements of the Greedy Strategy (Part 2)
- Grokking Algorithms: 8 Greedy Algorithms
- Competitive Programming: 3.4 Greedy
- Competitive Programming: 9.24 Min Path Cover on DAG
- Skiena: 10 How to Design Algorithms
Optional Deep Dive
- Skiena: 8.4 War Story -- Evolution of the Lobster
- Skiena: 8.8 War Story -- What's Past Is Prolog
- Competitive Programming: 6.5 String Processing with Dynamic Programming
- Competitive Programming: 8.4 Problem Decomposition
Concept-to-Source Map
| Primary concept | Best source if stuck | Why this source |
|---|---|---|
| Optimal substructure: when a problem admits DP | CLRS: 14.3 Elements of Dynamic Programming (Part 1) | Most rigorous statement of the cut-and-paste argument |
| Overlapping subproblems: why naive recursion wastes work | CLRS: 14.3 Elements of Dynamic Programming (Part 2) | Best explanation of subproblem DAG and recomputation |
| Memoization vs tabulation trade-offs | CLRS: 14.3 Elements of Dynamic Programming (Part 3) | Direct comparison of the two implementations |
| Reconstructing the solution from a DP table | CLRS: 14.1 Rod cutting (Part 3) | Parent-array reconstruction in full |
| Longest increasing subsequence | Skiena: 8.3 Longest Increasing Sequence | Both O(n^2) and O(n log n) algorithms with operational detail |
| Edit distance and sequence alignment | Skiena: 8.2.2 Edit Distance by Dynamic Programming | Clearest exposition of the 2D recurrence and reconstruction |
| Knapsack variants and state design | Skiena: 13.10 Knapsack Problem | Primary source for 0/1 DP and pseudo-polynomial analysis |
| Interval DP: matrix chain, optimal BST, balloon burst | CLRS: 14.2 Matrix Chain Multiplication (Part 1) | Canonical interval DP with fill-order discussion |
| Tree DP: independent set, diameter, rerooting | Competitive Programming: 9.22 Max Weighted Independent Set | Clean post-order recurrence on a tree |
| Bitmask DP: TSP and subset-enumeration | Skiena: 8.7 Limitations of DP (TSP) | Motivates Held-Karp and bounds its applicability |
| Proving greedy correctness / recognizing greedy fails | CLRS: 15.1 Activity Selection (Part 1) | Best first exchange-argument proof |
| DP on DAGs and graph-based DP | Competitive Programming: 9.24 Min Path Cover on DAG | Concrete DAG-DP example |
| Choosing the right paradigm for optimization problems | Skiena: 10 How to Design Algorithms | Best prose on paradigm selection across problem types |