COMP90038 · Algorithms And Complexity
Dynamic Programming
The optimisation paradigm for problems with two properties: overlapping sub-problems (the same smaller question is asked many times) and optimal substructure (an optimal whole is built from optimal parts). Instead of re-solving, you solve each sub-problem once and store its answer in a table, then build up to the final answer — bottom-up (fill the table in dependency order) or top-down (recurse with memoisation). The chapter works the canonical recurrences: the warm-up coin-row problem, the 0/1 knapsack (a 2-D weight×item table), and the two graph DPs the exam loves to hand-trace — Warshall's algorithm for transitive closure (boolean reachability, R(k) matrices) and Floyd's algorithm for all-pairs shortest paths (D(k) matrices), both Θ(n3) by relaxing through one intermediate vertex k at a time. It closes on a space optimisation: many DPs only need the previous row, so the table collapses to O(1) or O(n) space. Q1 hand-fills a Warshall R2 or a Floyd D1 round, so the “through vertex k” update rule must be reflexive.
What this chapter covers
- 01Overlapping sub-problems and optimal substructure — the two DP preconditions
- 02Bottom-up table vs top-down memoisation; coin-row warm-up
- 030/1 knapsack as a weight×item table
- 04Warshall's transitive closure (R(k)) — Θ(n3)
- 05Floyd's all-pairs shortest paths (D(k)); O(1)-space DP tricks
Worked example: one Floyd round
- +1The Floyd update. For each pair (i, j), set d(i,j) = min(d(i,j), d(i,k) + d(k,j)) — can we get from i to j cheaper by routing through k?
- +2Apply k = 2 to the pair (1, 3). d(1,3) = min(11, d(1,2) + d(2,3)) = min(11, 4 + 2) = min(11, 6).
- +1Result. The new shortest distance d(1,3) = 6, via the path 1→2→3, improving on the direct 11.
Key terms
- Dynamic programming
- An optimisation technique for problems with overlapping sub-problems and optimal substructure: solve each sub-problem once, store it, and combine stored answers. Bottom-up table-filling and top-down memoisation are the two implementations.
- Overlapping sub-problems
- The property that a recursive solution re-asks the same smaller questions many times. It is what makes memoisation pay off — without it (as in mergesort), plain divide-and-conquer is already efficient and DP gives no benefit.
- Memoisation
- Top-down DP: write the natural recursion but cache each sub-problem's result the first time it is computed, returning the cached value on later calls. Same asymptotics as the bottom-up table, with the recursion's call structure.
- Warshall's algorithm
- Computes the transitive closure (which vertices can reach which) of a digraph by a DP over an intermediate vertex k: R(k)[i][j] = R(k−1)[i][j] OR (R(k−1)[i][k] AND R(k−1)[k][j]). Θ(n3).
- Floyd's algorithm
- Computes all-pairs shortest paths by the same intermediate-vertex DP: d(k)[i][j] = min(d(k−1)[i][j], d(k−1)[i][k] + d(k−1)[k][j]). Θ(n3); the weighted analogue of Warshall.
Dynamic Programming FAQ
When can I use dynamic programming?
When the problem has overlapping sub-problems (the same smaller instances recur) and optimal substructure (an optimal solution is composed of optimal sub-solutions). If sub-problems do not overlap, plain divide-and-conquer is already efficient; if substructure fails, DP gives the wrong answer.
What is the difference between Warshall's and Floyd's algorithms?
They are the same DP skeleton over an intermediate vertex k. Warshall computes boolean reachability (transitive closure) with OR/AND; Floyd computes shortest-path distances with min and addition. Both are Θ(n3) and both are favourite Q1 hand-trace targets.
How do DP problems use only O(1) or O(n) space?
When each table entry depends only on the previous row (or a constant number of earlier entries), you can overwrite in place or keep just one or two rows instead of the whole 2-D table. The coin-row and many 1-D DPs collapse to O(1) extra space this way without changing the answer.
Exam move
Make the “through vertex k” update rule reflexive, because Q1 hand-fills a Warshall R2 or a Floyd D1 round — Θ(n2) cells per round, where one wrong min/OR cascades. Practise stating the two DP preconditions (overlapping sub-problems + optimal substructure) in a Q2 justification, and recognising “all-pairs shortest paths” → Floyd and “reachability” → Warshall on sight in a design question. Learn the coin-row and knapsack recurrences as templates, and know which DPs collapse to O(1) space.
