Unit 5.1 · about 3 h
119 / 324Dynamic programming states, transitions and base cases
Every later card asks for the state first. If the state misses information the future needs, no memo or loop order can fix it.
- derive
You can now
- Write the state, recurrence, base cases and evaluation order for an unseen optimization problem before coding.
- Explain why optimal substructure and overlapping subproblems are both needed, using a negative example.
- Prove a recurrence considers every feasible optimum and never admits an invalid solution.
Covers
- State sufficiency and overlapping subproblems
- Optimal substructure and transition completeness
- Base cases, invalid states and initialization
Study, in this order
4 steps
- Smart recursion first, tables secondAlgorithms - dynamic programming
Section 3.4, The Pattern: Smart Recursion (pp. 105-107): specification plus solution, then subproblems, dependencies and evaluation order
- Text segmentation recurrenceAlgorithms - dynamic programming
Section 3.3 (p. 105): \(\operatorname{Splittable}(i)\) recurrence with base \(\operatorname{Splittable}(n+1) = \text{True}\) and \(O(n^2)\)
IsWordcalls - Optimal substructure by contradictionAlgorithms - dynamic programming
Section 3.7 Edit Distance, Recursive Structure (pp. 111-112): remove the last column of an optimal alignment, and the rest is optimal for the prefixes, proved by contradiction
- The two conditions with a negative exampleDSA Handbook - dynamic programming
What dynamic programming actually is: optimal substructure plus overlapping subproblems, with merge sort as the negative example
Depth · The opening says naive
fib(43)makes about 433 million calls; that is \(F(43)\), the return value. Erickson Section 3.1 gives the call count \(2F(n+1) - 1\), about 1.4 billion for \(n = 43\).
Focus on
- A state is sufficient when the future depends only on the state, never on how it was reached. \(\operatorname{Splittable}(i)\) needs only the suffix start \(i\).
- Optimal substructure is a claim about subproblems: removing the last column of an optimal alignment leaves an optimal alignment of the shorter prefixes.
- Base cases define the empty input. \(\operatorname{Splittable}(n+1) = \text{True}\) and \(\operatorname{Edit}(0, j) = j\) are load-bearing, not boilerplate.
- Merge sort has optimal substructure without overlapping subproblems, so a memo never hits. Both conditions must hold.
Reproduce closed-book
True. Change OR to a sum to count segmentations: 2 (ARTIST.OIL and ART.IS.TOIL).Traps
- Adding a state dimension for safety. Extra dimensions multiply the table for no gain; keep the smallest sufficient state.
- A state that forgets a constraint the future needs. On a circle of houses (LC 213), \(\text{dp}\) over the index alone can rob both the first and the last house; run the line twice, without the first house and without the last, or add "first house robbed" to the state.
- Writing the table before the recurrence. Without a one-sentence English specification of the subproblem you cannot tell a wrong recurrence from a wrong loop order.
Practice
Solve \(n = 2\) (answer 2) and \(n = 5\) (answer 8) by hand from \(\text{ways}[n] = \text{ways}[n-1] + \text{ways}[n-2]\) with \(\text{ways}[0] = \text{ways}[1] = 1\), then submit.
Write the state, transition and base cases on paper first. After submitting, compare with the DSA Handbook dp-1d Climbing Stairs section.
Derive \(\text{dp}[i] = \max(\text{dp}[i-1], \text{dp}[i-2] + \text{nums}[i])\) and test [2,1,1,2] (answer 4) before submitting.
The alternating parity pick returns 3 on [2,1,1,2] and is wrong. After submitting, read the AlgoMaster House Robber lesson (https://algomaster.io/learn/dsa/house-robber).
Self-test
-
Why is \(\operatorname{Splittable}(n+1) = \text{True}\) the correct base case?
An empty suffix needs no words, so it segments trivially. The recurrence checks \(\operatorname{SplitTable}[j+1]\) for \(j = n\), which reads exactly this cell. -
Merge sort splits, recurses and combines. Why is it not dynamic programming?
Its halves share no subproblems, so a memo never hits. Optimal substructure alone does not make DP; overlapping subproblems must also hold. -
How does the edit-distance proof show three predecessors are enough?
By contradiction on the last alignment column: it must be an insertion, a deletion or a substitution. If the remaining prefixes had a shorter edit sequence, gluing the last column back would shorten the whole, contradicting optimality. -
Your recurrence passes the samples but you cannot state its subproblem in one English sentence. What do you do?
Stop and write the specification first. Without it a wrong recurrence and a wrong loop order look identical in the test output.
Completion criterion
Stop when
You write state, recurrence, base cases and order for Climbing Stairs and House Robber without notes, and can show why the parity-greedy pick fails on [2,1,1,2].
Leads to
- 5.2 Memoization, tabulation and dependency order Fill the recurrence by memo or by table once the state is fixed.
- 4.3 Greedy choice, optimal substructure and exchange arguments Separate DP recurrences from greedy-choice arguments with proofs or counterexamples.
Comes after
- 1.8 Prefix sums, difference arrays and prefix plus hashPrefix recurrences become DP states with more structure.
- 4.1 Recursion contracts, backtracking and sound pruningRepeated subproblems turn this chassis into memoized search later.
- 4.3 Greedy choice, optimal substructure and exchange argumentsOptimal substructure without a safe greedy choice forces dynamic programming.
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.
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.
- 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.