Unit 5.3 · about 3 h
121 / 324Solution reconstruction and rolling state
An optimum without a witness cannot be checked. Compression that deletes the decisions trades checkability for memory.
- implement
You can now
- Reconstruct an optimal witness by walking parent pointers back from the answer cell.
- Decide whether rolling compression preserves dependencies and reconstruction, and state what is lost.
- Implement length-only rolling rows and full-table recovery without mixing the two.
Covers
- Solution reconstruction and independently checkable outputs
- Rolling state and dependency-preserving compression
Study, in this order
3 steps
- Backtracking the LCS tableDSA Handbook - dynamic programming
Recovering the actual subsequence: backtrack from \((m, n)\) with one tie-break used in both passes; \(O(\min(m, n))\) space via row reuse
- Rolling compression and its costDSA Handbook - dynamic programming
Rolling-pair compression: from \(O(n)\) to \(O(1)\) space, including the warning that compression makes traceback impossible
- Linear-space recovery by splittingErickson lecture note D - Advanced Dynamic Programming
Section D.1, Saving Space: Divide and Conquer: forward-backward split with the Half table to recover the edit sequence in \(O(m + n)\) space
Focus on
- Fill and backtrack must share one tie-break. Mixed comparators walk a path the fill never scored.
- A rolling row keeps only the previous row, so the parent chain is gone. Length-only compression and reconstruction exclude each other without a Hirschberg split.
- Backtrack cost is \(O(m + n)\): every step decrements \(i\), \(j\), or both, so no cell is revisited.
Reproduce closed-book
Traps
- Keeping one row and then trying to backtrack through it. Old rows are gone; recovery needs the full table or a Hirschberg split.
- Using strict greater-than in the fill and greater-or-equal in the backtrack. Either comparator is fine alone; mixing them walks an unscored path.
- Reading
text1[i]instead oftext1[i-1]inside a 1-indexed table. The one-character test(a, a)raisesIndexErrorat \(i = 1\) and exposes the shift.
Practice
LeetCode 583 - Delete Operation for Two Strings
Reduce to LCS with \(\text{answer} = m + n - 2k\); check \((\text{sea}, \text{eat}) = 2\) and \((\text{leetcode}, \text{etco}) = 4\), then submit.
After submitting, compare with the DSA Handbook lcs reduction section for LC 583.
Self-test
-
Why does the rolling LCS return the length but not the string?
The backtrack walks rows in reverse, and the rolling form discarded every row but the last two. The parent pointers lived in the discarded rows. -
Two valid LCS strings exist for one input. Is that a bug?
No. Ties in \(\max(\text{up}, \text{left})\) admit several optimal paths. Any one of them is a correct LCS; enumerating all is a different, exponential-output problem. -
What does the Hirschberg split add over rolling rows?
The witness in linear space. Rolling rows give the length in \(O(\min(m, n))\) space; the midpoint split recurses on both halves to also recover the sequence in \(O(m + n)\) space at a constant time factor. -
House Robber rolling pair: can you still name the robbed houses?
No. The pair kept values, not decisions. Keep a boolean choice array or the fulldpcolumn to reconstruct the set.
Completion criterion
Stop when
Your backtrack returns length 4 plus a valid witness on the textbook pair, and your rolling form agrees on the length.
Mark passed, then open 5.4 Only mark this when you can do it without notes.Leads to
- 5.4 Sequence and string dynamic programming Recover witnesses on the string table where ties create several valid answers.
- 5.5 Grid, path and interval dynamic programming Carry the keep-or-compress decision to grid and interval tables.
Comes after
- 5.2 Memoization, tabulation and dependency orderKeep the table when you must reconstruct; compress only the value.
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.
- 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.
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.
- 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.
- 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 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.