Module 4: Dynamic Programming & Optimization: Case Studies
Dynamic programming is a modeling discipline: define state, transition, order, and proof before optimizing code.
Case Study 1: Subscription Plan Optimization
Scenario: A streaming service wants to choose discounts for each month to maximize yearly revenue while respecting churn risk. A greedy approach picks the best-looking monthly discount independently, but long-term retention depends on previous choices.
Source anchor: MIT OpenCourseWare dynamic programming lecture.
Module concepts:
- optimal substructure
- state definition
- recurrence design
- greedy vs DP
Wrong Approach
Pick the best discount for the current month and assume repeated local wins create a global optimum.
Better Approach
Define state as (month, retentionSegment, previousDiscount) if the previous decision affects churn. Write a recurrence that compares choices for the next month, caches subproblems, and reconstructs the chosen discount path.
Tradeoff Table
| Choice | Gain | Cost |
|---|---|---|
| Greedy monthly choice | Simple and explainable | Misses delayed effects |
| DP over state | Finds global optimum under model | State space can grow quickly |
| Simulation only | Captures uncertainty | Harder to prove optimality |
Failure Mode
The discount plan maximizes the first month and loses high-value users later.
Required Artifact
Write the DP state, recurrence, base cases, decision reconstruction, and one small hand-solved table.
Project / Capstone Connection
Use this artifact for any project optimization problem with decisions that affect later choices.
Case Study 2: Memoization Key in a Route Planner
Scenario: A delivery planner computes the cheapest route with constraints on remaining fuel and package priority. The first memoized recursion keys only by current location, so it reuses results across different fuel states.
Source anchor: MIT OpenCourseWare dynamic programming lecture.
Module concepts:
- memoization
- complete state
- correctness before performance
- overlapping subproblems
Wrong Approach
Cache by the most obvious variable and celebrate the speedup.
Better Approach
List every variable that can change the answer: location, remaining fuel, delivered set or compressed mask, time window, and priority constraints. Cache only on a complete state representation, then measure hit rate and memory growth.
Tradeoff Table
| Choice | Gain | Cost |
|---|---|---|
| Incomplete key | Fast but wrong | Reuses invalid answers |
| Complete key | Correct caching | More memory |
| No memoization | Simple semantics | Repeats subproblems |
Failure Mode
The planner returns a route that is cheap only for a different remaining-fuel condition.
Required Artifact
Produce a memoization-key audit listing state variables, why each affects the answer, and tests where omitting it fails.
Project / Capstone Connection
Use this audit for recursive DP, graph search caches, and memoized parsers.
Case Study 3: Grid DP for Warehouse Picking
Scenario: A warehouse robot moves through aisles with blocked cells and pick rewards. The team writes recursive search over every path from start to exit and hits exponential growth.
Source anchor: The module's sequence and grid DP lessons.
Module concepts:
- grid DP
- transition order
- obstacle handling
- path reconstruction
Wrong Approach
Search all possible paths and keep the best reward found.
Better Approach
If movement is acyclic, define dp[row][col] as the best reward reaching that cell, transition from legal predecessors, and store parent pointers for path reconstruction. If movement can cycle, recognize that it is no longer a simple grid DP and change the model.
Tradeoff Table
| Choice | Gain | Cost |
|---|---|---|
| Exhaustive path search | Direct problem statement | Exponential blowup |
| Grid DP | Polynomial for acyclic movement | Needs movement restrictions |
| Graph shortest/longest path model | More general | Requires cycle analysis |
Failure Mode
The recurrence silently assumes no cycles, but the robot can move backward.
Required Artifact
Create a grid table with blocked cells, base case, transition arrows, filled DP values, and reconstructed path.
Project / Capstone Connection
Use the same filled-table explanation in the DP section of the algorithms portfolio.
Case Study 4: Space Optimization That Breaks Reconstruction
Scenario: A text comparison tool computes edit distance and must also show the edits. A developer optimizes from a full table to two rows, then cannot reconstruct insertions, deletions, and substitutions.
Source anchor: The module's sequence-DP and optimization-tradeoff concepts.
Module concepts:
- sequence DP
- space optimization
- reconstruction
- tradeoff analysis
Wrong Approach
Optimize memory immediately because the recurrence only needs the previous row.
Better Approach
Separate score computation from explanation requirements. Two-row DP may be enough for distance only; edit script reconstruction needs parent information, checkpointing, or a divide-and-conquer reconstruction method.
Tradeoff Table
| Choice | Gain | Cost |
|---|---|---|
| Full table | Easy reconstruction | Higher memory |
| Two-row table | Low memory | Loses parent path |
| Checkpointed reconstruction | Balanced memory | More complex implementation |
Failure Mode
The service returns the correct distance but cannot explain which edits produced it.
Required Artifact
Write a memory/reconstruction decision note with required output, table size, parent storage, and accepted tradeoff.
Project / Capstone Connection
Use this note before optimizing away information that tests or users need.
Source Map
| Source | Use it for |
|---|---|
| MIT OpenCourseWare dynamic programming lecture | DP framing: exhaustive search plus memoized subproblem structure. |