Unit 5.9 · about 4 h
127 / 324Dynamic programming as shortest paths, formulations and limits
DP transfers to batching, caching and allocation. The skill is recognizing the state there, plus knowing when the state space is too large for exact methods.
- explain
- derive
You can now
- Reformulate a scheduling, batching, caching or allocation narrative as DP or shortest path on a DAG.
- State when exact optimization is infeasible and bound the heuristic or relaxation you use instead.
- Reject tempting greedy or insufficient-state proposals with concrete counterexamples.
Covers
- Dynamic programming as a DAG or shortest-path problem
- Scheduling, caching, batching and allocation formulations
- Exact, heuristic and approximate boundaries
Study, in this order
4 steps
- Coin change as the allocation familyDSA Handbook - dynamic programming
How minimum coins, count of ways and minimum cost share one recurrence: the allocation family with the reuse direction
Depth · Reread for the allocation framing only; the loop mechanics belong to the knapsack unit.
- DP on an implicit DAGDSA Handbook - dynamic programming
Strict-increase predicate: the implicit DAG and DFS-with-memo (LC 329); monotone moves make the cell graph acyclic
- Greed is stupid without a proofAlgorithms - dynamic programming
Section 3.5 (pp. 107-108): Warning: Greed is Stupid, with the shortest-prefix text-segmentation counterexample
- When exact scheduling is infeasibleErickson lecture note J - Approximation Algorithms
Section J.1, Load Balancing: NP-hardness by reduction from Partition,
GreedyLoadBalance, and Theorem J.1 with its factor-2 proof
Focus on
- DP works on the cell graph because monotone moves or a strict predicate make it acyclic. Arbitrary four-directional movement is not DP.
- Coin change is allocation: amount is the budget, denominations are unit costs, and the inner-loop direction is the reuse policy.
- Partition makes exact load balancing NP-hard, so the greedy 2-approximation with its stated bound is the honest answer at scale.
Reproduce closed-book
False on \(s = \text{abcd}\) with dict [ab, abc, cd] while tabulated DP returns True. GreedyLoadBalance on jobs [5,5,4,4,3,3,3] with \(m = 2\) gives makespan 15 against optimal 14, inside the factor-2 bound. State both inputs and all three expected outputs.Traps
- Calling the greedy 2-approximation optimal. The bound is a worst-case factor, not an equality claim; 15 versus 14 on the demo inputs shows the gap.
- Modeling allocation without stating the reuse policy. One loop direction means each unit once; the other means unlimited reuse. Name it.
- Running memoized DFS on a cyclic move graph. With four-directional moves and no strict predicate, a call can reach a cell still on the stack, and the memo caches a value computed from an unfinished one. Prove the graph acyclic first, or switch to a shortest-path algorithm.
Practice
LeetCode 1235 - Maximum Profit in Job Scheduling
Solve tag-hidden. Example 1 returns 120 and example 2 returns 150. First show that earliest-finish greedy keeps 90 on example 1, then sort by end time and write \(\text{dp}\) over jobs with a binary search for the last compatible job.
Write the state and the take-or-skip recurrence before coding. After submitting, read the AlgoMaster Maximum Profit in Job Scheduling lesson (https://algomaster.io/learn/dsa/maximum-profit-in-job-scheduling).
Solve tag-hidden. Check (leetcode, [leet, code]) = True and (catsandog, [cats, dog, sand, and, cat]) = False, then submit.
Exhibit the abcd longest-prefix failure in your notes. After submitting, compare with the DSA Handbook decode-word-break page and the AlgoMaster Word Break lesson (https://algomaster.io/learn/dsa/word-break).
Self-test
-
Word Break
abcdwith[ab, abc, cd]: why does longest-prefix greedy fail?It takesabcfirst and strandsd. The valid splitab + cdneeds the shorter first piece; only the OR-over-splits recurrence compares both. -
Why is load balancing NP-hard, in one reduction?
Partition reduces to two-machine makespan: the jobs split evenly iff some assignment reaches \(\text{total}/2\). Exact optimization at scale is infeasible, which is why the greedy bound matters. -
State the greedy load-balance bound with its two observations.
Makespan at most twice optimal. \(\operatorname{OPT}\) covers the longest job and the average load; the last job on the bottleneck machine adds at most one \(\operatorname{OPT}\) to a below-\(\operatorname{OPT}\) base. -
A batching problem has \(10^6\) jobs and 64 machines. Exact DP or greedy?
Greedy with the stated bound, then measure. Load balancing is NP-hard, so exact search over assignments is infeasible at this size;GreedyLoadBalanceis within a factor of 2, and sorting the jobs longest-first tightens the bound.
Completion criterion
Stop when
Both tag-hidden solutions are accepted, and you can exhibit the earliest-finish and longest-prefix counterexamples plus the exact-versus-approximate boundary without notes.
Mark passed, then open 1.1 Only mark this when you can do it without notes.Leads to
- 3.6 Dijkstra, Bellman-Ford and negative cycles Read the Bellman-Ford DP formulation as the same recurrence on graphs.
- stage 06 · Systems Foundations Carry DP batching and allocation formulations into systems design.
Comes after
- 3.1 Graph modeling, representations and state graphsMeet state graphs again as shortest paths and DP over DAGs.
- 3.4 Topological ordering and strongly connected componentsTopological order is the evaluation order for DP on DAGs; carry it into recurrence dependencies.
- 3.6 Dijkstra, Bellman-Ford and negative cyclesBellman-Ford is dynamic programming over edge count; carry the relaxation-as-DP frame into recurrences.
- 3.9 Flow and matching at recognition depthReductions are the shared move: this unit reduces matching to flow the way later units reduce problems to shortest paths.
- 5.7 Knapsack, subset and bitmask dynamic programmingRead coin change as allocation and state when the subset space is too large.
- 5.8 Recurrence proofs and differential validationCarry proof and counterexample habits to transfer problems.
Resources for this unit
- DSA Handbook - dynamic programming Study Part 9 in order from state and recurrence through sequence, grid, tree and bitmask families. For every example, close the page and reconstruct the state, transition and evaluation order.
- Algorithms - dynamic programming Use the dynamic-programming chapter to derive states and recurrences from first principles and to separate DP from greedy reasoning and shortest paths.
- Erickson lecture note J - Approximation Algorithms Read Section J.1 (Load Balancing) for the Partition reduction that makes exact scheduling NP-hard, the
GreedyLoadBalanceheuristic, and Theorem J.1 with its factor-2 proof.
Also in this section
- AlgoMaster DSA - dynamic programming slice Attempt Coin Change, Longest Common Subsequence and House Robber III cold. Write the state, transition, base case and evaluation order first; compare against brute force on small inputs and reconstruct a witness when available.
- Hypothesis - exhaustive and differential DP tests Generate small valid instances, compare memoized, tabulated and exhaustive results, and retain shrunk failures for wrong state, base case, order and compression defects.
- NeetCode - unseen mixed problems Use two tag-hidden mixed problems as the final transfer test. One must require rejecting a tempting greedy or insufficient-state solution with a counterexample.
- Python sys: recursion limit Read
sys.getrecursionlimitandsys.setrecursionlimit: the limit guards the C stack and its safe maximum is platform-dependent. Check the default withgetrecursionlimit(1000 on CPython 3.13), raise it once for memoized DP, or switch to tabulation for deep inputs. - Erickson lecture note D - Advanced Dynamic Programming Read Section D.1 (Saving Space: Divide and Conquer) for the Hirschberg Half-table split that recovers an optimal edit sequence in \(O(m + n)\) space.