Dynamic programming
Introduit
Vocabulaire
| English | Sens |
|---|---|
| dynamic programming | dynamic programming |
| dependency order | dependency order |
| DP table | DP table |
English
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}
Pratique
The DP design is —
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
Three parts: what a cell means, where it starts, which direction to fill.
English
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}
Pratique
Naive fib(30) makes — calls
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
The call count is itself Fibonacci-exponential; memoised it is 29 subproblems.
English
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}
Pratique
Capacity 7 with items (1,1)(3,4)(4,5)(5,7): dp[7] = —
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
Items 2 and 3: weight 7, value 9.