Dynamic programming
Introduced
Vocabulary
| English | Meaning |
|---|---|
| dynamic programming | Solving overlapping subproblems and storing their results for reuse. |
| dependency order | An order in which every needed subproblem result is available before it is used. |
| DP table | A table storing solutions to subproblems in a dynamic-programming algorithm. |
Remember, do not recompute
- Dynamic programming solves each overlapping subproblem once, stores it, and builds larger answers from stored ones. The design is three things: the recurrence, the base cases, the dependency order to fill the DP table.
{exercise:uni-cs1004-dp}
Practice
The DP design is —
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Three parts: what a cell means, where it starts, which direction to fill.
The exponential that was not
- Naive Fibonacci recomputes: $F(30)$ makes 2,692,537 calls — the call count obeys the same recurrence, exponential. Memoised: 29 subproblems, $\Theta(n)$.
- The coin table (coins 1, 3, 4): $dp[i] = 1 + \min(dp[i - c])$ over usable coins — $dp[6] = 2$ (3+3), where greedy pays 3.
{exercise:uni-cs1004-fib}
Practice
Naive fib(30) makes — calls
Difficulty 1/5 · 100 coins + a small bonus on first completion today
The call count is itself Fibonacci-exponential; memoised it is 29 subproblems.
Knapsack, small and exact
- Capacity 7, items (1,1), (3,4), (4,5), (5,7): the table over capacity gives $dp[7] = 9$ (items 2 and 3: weight 7, value 9).
- Every cell is a decision with a reason — the table IS the explanation. Iterate the direction the arrows point, and never read an unwritten cell.
{exercise:uni-cs1004-knapsack}
Practice
Capacity 7 with items (1,1)(3,4)(4,5)(5,7): dp[7] = —
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Items 2 and 3: weight 7, value 9.