Dynamic programming
Introducido
Vocabulario
| English | Significado |
|---|---|
| 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. |
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}
Práctica
The DP design is —
Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy
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}
Práctica
Naive fib(30) makes — calls
Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy
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}
Práctica
Capacity 7 with items (1,1)(3,4)(4,5)(5,7): dp[7] = —
Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy
Items 2 and 3: weight 7, value 9.