Unit 5.5 · about 4 h
123 / 324Grid, path and interval dynamic programming
Iteration direction follows the dependency direction. Survival predicates read successors, so the loop runs backward.
- derive
- implement
You can now
- Derive forward fills for counting and min-sum grids and backward fills for survival predicates.
- Derive interval recurrences that try the last operation in \([l, r]\) and fill by increasing length.
- Implement both families with brute-force differential tests on small grids and intervals.
Covers
- Grid, path and interval dynamic programming
Study, in this order
3 steps
- Forward fills and the backward twistDSA Handbook - dynamic programming
The pattern on LC 62 (\(3 \times 7\) worked example, answer 28) and The twist on LC 174 (backward recurrence with the \(\max(\ldots, 1)\) clamp and reversed loops)
- Interval DP with the last operationDSA Handbook - dynamic programming
The pattern: \(\text{dp}[l][r]\) tries the LAST operation in the range; Worked example: \(\text{nums} = [3, 1, 5, 8]\); What CLRS calls matrix-chain multiplication
Depth · The chapter labels LC 1039 as Matrix Chain Multiplication; on LeetCode it is Minimum Score Triangulation of Polygon, which has the same interval shape.
- Interval order on optimal search treesAlgorithms - dynamic programming
Section 3.9 (pp. 117-119): \(\operatorname{OptCost}(i, k)\) interval recurrence and its three valid evaluation orders: by diagonal, row by row from the bottom up, and column by column from left to right
Focus on
- Forward DP fails Dungeon Game because HP-needed-at-entry depends on the suffix, not the prefix. Backward state \(\text{dp}[i][j]\) is HP needed on entering \((i, j)\).
- The \(\max(\ldots, 1)\) clamp is the survival predicate per cell, not a guard. Dropping it admits zero-HP entries the knight cannot use.
- Interval cells depend on strictly shorter intervals, so length-ascending fill is the order. Any single direction that respects shorter-first works.
Reproduce closed-book
unique_paths(3, 7) = 28, min_path_sum([[1,3,1],[1,5,1],[4,2,1]]) = 7, dungeon([[-2,-3,3],[-5,-10,1],[10,30,-5]]) = 7, burst([3,1,5,8]) = 167. State the grid sizes and all four expected outputs.Traps
- Copying the LC 64 idea into Dungeon Game: maximize the path sum, then read the HP it needs. On the problem's own example the max-sum path (down, down, right, right; sum 28) needs 8 HP, but right, right, down, down needs 7.
- Continuing the LC 63 base row past the first obstacle. Cells past a top-row wall are unreachable; the base loop must
break, notcontinue. - Filling interval tables row-major left to right. Cell \((l, r)\) reads \((l, k)\) and \((k+1, r)\), which a plain row-major pass may not have written; iterate by length.
Practice
Check that a 3 by 7 grid gives 28 paths and a 3 by 2 grid gives 3, then submit.
Fill row-major and state the read set above the loop. After submitting, compare with the DSA Handbook grid-dp LC 62 section.
Check [[-2,-3,3],[-5,-10,1],[10,30,-5]] = 7 and [[0]] = 1, then submit.
Iterate backward with the clamp. After submitting, compare with the DSA Handbook grid-dp LC 174 section and the AlgoMaster Dungeon Game lesson (https://algomaster.io/learn/dsa/dungeon-game).
Self-test
-
Why does Dungeon Game iterate bottom-right to top-left?
\(\text{dp}[i][j]\) reads \(\text{dp}[i+1][j]\) and \(\text{dp}[i][j+1]\). Reversed row-major order keeps both reads on computed cells; forward order reads sentinels. -
Unique Paths \(3 \times 7\) is 28. Name the closed form and when it breaks.
\(C(m+n-2, m-1) = C(8, 2) = 28\). It breaks with obstacles, weights or backward predicates; the DP survives all three. -
Why does Burst Balloons try the last burst in \([l, r]\) instead of the first?
Bursting \(k\) first changes the neighbors of the rest, so subintervals are not independent. Bursting \(k\) last fixes its neighbors to the interval boundaries, which splits \([l, r]\) into independent \([l, k-1]\) and \([k+1, r]\). -
A forward fill keeps, per cell, the smallest starting HP needed so far. Why can it fail?
A predecessor that needed less HP so far may arrive with less HP left, and one number cannot keep both. On[[-2,-1,-1],[-3,-1,0],[2,0,-3]]the forward fill answers 8 while the backward fill gives 7.
Completion criterion
Stop when
The four reproduce numbers come out of a blank file, and you can state each recurrence read set and loop direction.
Mark passed, then open 5.6 Only mark this when you can do it without notes.Leads to
- 5.6 Tree dynamic programming Replace the grid order with post-order on trees.
- 5.7 Knapsack, subset and bitmask dynamic programming Move from spatial intervals to capacity and subset state.
Comes after
- 5.3 Solution reconstruction and rolling stateCarry the keep-or-compress decision to grid and interval tables.
- 5.4 Sequence and string dynamic programmingMove the prefix-pair machinery to grids and intervals.
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.