Einführung in dynamische Programmierung
Überlappende Teilprobleme und optimale Teilstruktur: exponentielle Rekursion durch Merken der Antworten (Memoisierung) in polynomiale Zeit verwandeln.
Deutsche Übersetzung in Arbeit
Diese Lektion ist noch nicht ins Deutsche übersetzt und wird daher auf Englisch angezeigt. Der Rest der Seite ist vollständig lokalisiert.
Auf dieser Seite
Dynamic programming has a fearsome reputation, but the core idea is simple: don't solve the same subproblem twice. DP is just recursion plus memory. Once you can spot the two conditions that make it apply and add a cache, exponential solutions collapse to polynomial ones.
The two conditions
DP applies when a problem has both:
- Overlapping subproblems - the recursion solves the same smaller problems repeatedly.
- Optimal substructure - the optimal answer is built from optimal answers to subproblems.
Fibonacci is the canonical illustration of the waste (and the fix). Naive recursion recomputes the same values exponentially:
// naive: O(2^n) — fib(5) recomputes fib(3) twice, fib(2) three times, ...
int fib(int n) {
if (n <= 1) return n;
return fib(n - 1) + fib(n - 2); // massive recomputation
}Memoization: recursion with a cache
Memoization (top-down DP) keeps the natural recursion but remembers each subproblem's answer the first time it's computed, so repeats are instant lookups. One cache turns O(2^n) into O(n):
// memoized: O(n) — each fib(k) computed once
int fib(int n, Integer[] memo) {
if (n <= 1) return n;
if (memo[n] != null) return memo[n]; // already solved
return memo[n] = fib(n - 1, memo) + fib(n - 2, memo); // solve once, store
}Tabulation: build the table bottom-up
Tabulation (bottom-up DP) flips the direction: instead of recursing down, iterate from the base cases up, filling a table where each entry uses earlier ones. No recursion, no stack:
// tabulated: O(n) time, O(1) space (only the last two values needed)
int fib(int n) {
if (n <= 1) return n;
int prev = 0, curr = 1;
for (int i = 2; i <= n; i++) {
int next = prev + curr; // each value from the two before it
prev = curr; curr = next;
}
return curr;
}Both give O(n); memoization is closer to the natural recursion (easier to derive), while tabulation avoids recursion overhead and often allows space optimization. Most DP solutions can be written either way - derive it recursively with memoization, then convert to a table if needed.
How to approach any DP
- Write the brute-force recursion (the 'try everything' solution). 2. Notice it recomputes subproblems.
- Add a cache keyed by the recursion's parameters - that's memoization, and usually enough. 4. Optionally convert to bottom-up tabulation for speed/space. The hard part is step 1: defining the state and the recurrence. The memoization is mechanical.
Imagine each tax form needs figures from several other forms, which need figures from still others - and many forms feed into multiple places. If you recompute a sub-form every time it's referenced, you redo enormous work. Instead you keep a folder of completed forms: the first time you finish one, you file it; every later reference just pulls the finished copy. That folder is memoization - each subproblem solved once and reused - turning a mountain of duplicated arithmetic into a single pass.
Consider counting the number of distinct ways to climb n stairs taking 1 or 2 steps at a time. The recursion is ways(n) = ways(n-1) + ways(n-2). Explain why the naive recursion is exponential and how memoization makes it linear, and note what famous sequence this equals.
What two properties must a problem have for dynamic programming to apply?
Key takeaways
- Dynamic programming is recursion plus memory: solve each subproblem once and reuse the answer.
- It applies when a problem has overlapping subproblems and optimal substructure.
- Memoization (top-down) keeps the natural recursion but caches results, turning O(2^n) into O(n) for Fibonacci-like recurrences.
- Tabulation (bottom-up) fills a table from base cases upward, avoiding recursion and often enabling space savings.
- Approach: write the brute-force recursion, notice recomputation, add a cache keyed by the parameters - defining the state and recurrence is the hard part.