Module 4: Dynamic Programming & Optimization

Primary texts: The Algorithm Design Manual (Skiena, Ch. 8) and Introduction to Algorithms (CLRS, Ch. 14)
Selective support: Competitive Programming (Halim) and Algorithms (Sedgewick) for problem variety; Grokking Algorithms only as a friendly re-entry point when the CLRS/Skiena chapter feels opaque

This guide is the primary teacher. You do not need to read the dynamic programming chapters front-to-back to complete this module. You do need to become operationally strong at recognizing when a problem admits DP, designing a correct recurrence, choosing a table layout, and judging when greedy, DP, or a graph reformulation is the right paradigm.

---

Scope of This Module

This module is not a list of memorized DP problems. It is where optimization problems become something you design rather than recognize.

What it covers in depth:

• the two structural conditions (optimal substructure and overlapping subproblems) that license DP at all
• memoization versus tabulation, and the space/time trade-offs between them
• reconstructing the optimal object, not only its optimal value
• linear and sequence DP patterns: Fibonacci, LIS (O(n^2) and O(n log n) patience), edit distance, and the knapsack family
• two-dimensional DP on grids, on intervals (matrix chain, optimal BST, balloon burst), and on trees (independent set, diameter, rerooting)
• bitmask and digit DP, and the rule for when state compression is worth it
• greedy correctness via exchange arguments, and honest recognition when greedy fails
• DP on DAGs as a unifying framework (longest path, topological DP)
• choosing a paradigm deliberately: brute force, greedy, DP, or a graph/shortest-path reformulation

What it deliberately does not try to finish here:

• network flow and LP-style optimization (Module 3 handles flow sketches; later systems work handles LP)
• advanced online and approximation algorithms beyond brief mention
• convex-hull / monotone-queue DP optimizations beyond a named pointer

This is a heavy module. If you can recite five classical recurrences but cannot derive a new one from a problem statement, you are not done.

---

Before You Start

Answer these closed-book before starting the main path:

1. What is the difference between a recurrence that runs in exponential time and one that runs in polynomial time after caching?
2. Why does "greedy" sometimes give the right answer and sometimes not?
3. Given a recurrence T(n) = T(n-1) + T(n-2), how many distinct subproblems are there?
4. What does it mean to "reconstruct" a solution rather than just compute its cost?
5. When would you prefer O(n log n) with more code complexity over a clean O(n^2) solution?

Diagnostic Interpretation

4-5 solid answers

• You are ready for the full path.

2-3 solid answers

• Continue, but expect extra time in Clusters 1-2 (foundations and sequence DP).

0-1 solid answers

• Revisit Module 1 (recursion, recurrences, asymptotic analysis) before starting here. DP inherits all of that and adds state design on top.

---

What This Module Is For

Dynamic programming is the main tool in CS for turning exponential recursive search into polynomial or pseudo-polynomial computation. Later work repeatedly asks:

• can I express the answer as a recurrence over a small set of subproblems?
• does this problem have a greedy shortcut, or does greedy miss cases?
• can I reformulate the problem as a shortest/longest path on a DAG?
• what is the minimum state that captures "everything relevant" for the next decision?
• how do I reconstruct the actual choice sequence, not just its cost?

This module builds the optimization and recurrence-design skill needed for:

• interview and contest problems that hinge on a recurrence insight
• compiler, parser, and scheduler internals that use DP over trees and intervals
• bioinformatics and NLP code that reduces to edit distance or alignment
• resource-allocation and planning code where knapsack-like trade-offs appear
• systems work where you must distinguish "near-optimal fast" (greedy) from "exactly optimal" (DP) problems

You are learning to recognize structure and design algorithms that exploit it.

---

Concept Map

---

How To Use This Module

Work in order. Later clusters assume the state-design habits built in Cluster 1.

Cluster 1: DP Foundations

Order	Concept	Type	Focus
1	Optimal Substructure: When a Problem Admits DP	PRIMARY	The cut-and-paste argument and why it licenses DP
2	Overlapping Subproblems: Why Naive Recursion Wastes Work	PRIMARY	Counting distinct subproblems and seeing the recursion DAG
3	Memoization vs Tabulation: Trade-offs	PRIMARY	Top-down versus bottom-up, cost of recursion, fill order
4	Reconstructing the Solution From a DP Table	SUPPORTING	Parent pointers, back-tracking, and why the value alone is not enough

Cluster mastery check: Can you state why DP applies before you write any code, and can you recover the optimal choice sequence as well as its cost?

Cluster 2: Linear and Sequence DP

Order	Concept	Type	Focus
5	Fibonacci and the Rolling-Array Space Reduction	SUPPORTING	Smallest example where a full table is wasteful
6	Longest Increasing Subsequence: O(n^2) and O(n log n) Patience	PRIMARY	Two different state designs for the same problem
7	Edit Distance and Sequence Alignment	PRIMARY	The canonical two-sequence recurrence, with reconstruction
8	Knapsack Variants and State Design	PRIMARY	0/1, unbounded, and bounded knapsack; pseudo-polynomial complexity

Cluster mastery check: Can you write the recurrence, base cases, fill order, and reconstruction for each of LIS, edit distance, and 0/1 knapsack without looking them up?

Cluster 3: Grid, Interval, and Tree DP

Order	Concept	Type	Focus
9	Grid DP: Paths, Obstacles, Collect-Maximum	SUPPORTING	2D tabulation with boundary and obstacle handling
10	Interval DP: Matrix Chain, Optimal BST, Balloon Burst	PRIMARY	The "split point" pattern over contiguous ranges
11	Tree DP: Independent Set, Diameter, Rerooting	PRIMARY	DP that follows a tree's recursive structure

Cluster mastery check: Given an unfamiliar problem, can you decide whether its state is indexed by position, by interval, or by tree node, and justify your choice?

Cluster 4: Bitmask and Digit DP

Order	Concept	Type	Focus
12	Bitmask DP: TSP and Subset-Enumeration DP	PRIMARY	Encoding "which subset is used" as a bitmask index
13	Digit DP: Counting Numbers With Constraints	SUPPORTING	Fixing a number digit by digit with a "tight" flag
14	State Compression and When It Is Worth It	SUPPORTING	Recognizing when exponential state is actually small enough

Cluster mastery check: Can you tell whether a problem's natural state space is genuinely small (so bitmask DP works) or deceptively small (so it does not)?

Cluster 5: Greedy vs DP and Optimization Tradeoffs

Order	Concept	Type	Focus
15	Proving Greedy Correctness (Exchange Argument) vs Recognizing It Fails	PRIMARY	What it actually takes to trust a greedy solution
16	DP on DAGs and Graph-Based DP	PRIMARY	Every DP is a DAG; when to make that explicit
17	Choosing the Right Paradigm for Optimization Problems	PRIMARY	A decision process: brute force, greedy, DP, shortest path, or approximation

Cluster mastery check: Given an optimization problem, can you justify your paradigm choice with a short argument rather than pattern-matching?

Then work these practice pages:

Order	Practice path	Focus
1	DP Foundations and State Design Lab	Recognizing DP applicability, defining state, designing recurrence
2	Sequence and Grid DP Workshop	LIS, edit distance, knapsack, and 2D grid DP drills
3	Advanced DP and Optimization Clinic	Interval, tree, bitmask DP, and greedy-vs-DP decisions
4	Code Katas	Implementation drills: LIS n log n, edit distance with reconstruction, 0/1 knapsack, matrix chain, tree DP, bitmask TSP

Use Module Quiz after the concept and practice path. Use Reference and Selective Reading and Learning Resources only for targeted reinforcement.

---

Learning Objectives

By the end of this module you should be able to:

1. Verify that a problem exhibits optimal substructure and overlapping subproblems before writing a DP.
2. Convert a correct recursive formulation into a memoized or tabulated implementation with explicit fill order.
3. Reconstruct the optimal object (not only its value) using parent pointers or choice arrays.
4. Design states for LIS, edit distance, and knapsack variants without looking them up.
5. Recognize and implement interval DP, tree DP, and grid DP from problem descriptions.
6. Encode small-subset problems as bitmask DP and evaluate whether 2^n states are affordable.
7. Write a digit DP by fixing a prefix with a "tight" flag and enumerating the next digit.
8. Prove greedy correctness via an exchange argument or produce a counterexample that forces DP.
9. Reformulate DP problems as shortest/longest path on an implicit DAG when it clarifies the structure.
10. Choose deliberately between brute force, greedy, DP, and graph methods based on problem structure, not habit.

---

Outputs

• a DP notebook with at least 20 solved problems, each with its state definition, recurrence, base cases, fill order, and complexity written out
• at least 6 solutions that include solution reconstruction, not only the optimal cost
• one "state-design sheet" with at least 10 problems classified by state shape (position / interval / subset / digit / tree node)
• one "greedy counterexamples" sheet with at least 5 problems where a plausible greedy strategy fails, with the failing input
• one tested implementation repo containing: lis_nlogn, edit_distance, knapsack_01, matrix_chain, tree_dp_independent_set, and tsp_bitmask, each with unit tests
• one memo comparing memoization and tabulation implementations of the same problem, with measured stack/heap behavior
• one short writeup on a problem you solved with DP and re-solved as a longest-path on a DAG, showing the two are equivalent
• one mistake log naming at least 10 real errors such as state missed an index, off-by-one in fill order, forgot base case, greedy worked on examples but not on the real test, or used 0/1 loop direction for unbounded knapsack

---

Completion Standard

You have completed Module 4 when all of these are true:

• you can state the substructure and subproblem-overlap argument for a new problem in sentences
• you can define a state that captures "everything relevant" for the next decision
• you can derive a recurrence, base cases, fill order, and complexity without pattern-matching
• you can reconstruct the optimal object, not only its value
• you can explain why greedy works when it does and why it fails when it does not
• you can reformulate DP as longest-path-on-DAG when the shape is unclear
• you can choose a paradigm with an argument, not a guess

If you can solve the canonical problems but cannot defend why DP (rather than greedy or brute force) is the right tool, the module is not complete.

---

Reading Policy

• Concept pages are the main path.
• Local book chunks (CLRS Ch. 14, Skiena Ch. 8, Competitive Programming Ch. 3 and Ch. 8) are selective reinforcement, not a second syllabus.
• Read only if stuck means try the concept page, derive the recurrence yourself, and implement before reading more.
• Optional deep dive means advanced optimizations (SOS DP, divide-and-conquer DP, Knuth optimization) that are useful later but not required here.
• Because this is a heavy module, written derivations and tested implementations are required outputs, not optional enrichment.

---

Suggested Weekly Flow

Day	Work
1	Concepts 1-4 (Cluster 1) and one solved DP problem with full state-design writeup
2	Concepts 5-8 (Cluster 2): Fibonacci rolling array, LIS O(n^2) and O(n log n)
3	Implement edit distance with reconstruction and 0/1 knapsack with space reduction
4	Concepts 9-11 (Cluster 3): grid DP, interval DP (matrix chain), and one tree DP
5	Concepts 12-14 (Cluster 4): bitmask DP (TSP), digit DP, and state-compression criteria
6	Concepts 15-17 (Cluster 5) and the paradigm-selection decision process
7	Practice pages, quiz, mistake-log cleanup, and reconstruct-the-solution drills

---

Reference

If you need exact links into the local chunked books, use Reference and Selective Reading.

---

Build Your Own X — elective

DP shows up everywhere once you can see it. The Neural Network and LLM tutorials use backprop, which is literally DP over a computational graph. The Systems-phase Regex Engine uses memoized subset construction. See Build Your Own X overview for the full catalog.

Rich Learning Pages

Worked Examples | Guided Labs | Case Studies | Mistake Clinic | Reading Guide | Capstone Thread