Step 1 of 6
Memoization
Backtracking explores every possibility. Often, though, the same sub-question comes up again and again inside that search, and answering it from scratch every time is what makes the search slow. Dynamic programming (DP) is the fix: answer each distinct sub-question once, store the answer, and look it up the next time.
The classic example is the Fibonacci numbers: 0, 1, 1, 2, 3, 5, 8, 13, ..., where each number is the sum of the two before it. The definition translates straight into recursion, and that recursion is terribly slow:
#include <iostream>
#include <vector>
long long calls = 0;
long long fib_slow(int n) {
calls++;
if (n < 2) return n;
return fib_slow(n - 1) + fib_slow(n - 2);
}
long long fib_memo(int n, std::vector<long long>& memo) {
calls++;
if (n < 2) return n;
if (memo[n] != -1) return memo[n]; // solved before: reuse the answer
memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo);
return memo[n];
}
int main() {
long long a = fib_slow(30);
std::cout << "slow: fib(30) = " << a << " after " << calls << " calls\n";
calls = 0;
std::vector<long long> memo(31, -1); // -1 means "not solved yet"
long long b = fib_memo(30, memo);
std::cout << "memo: fib(30) = " << b << " after " << calls << " calls\n";
}
slow: fib(30) = 832040 after 2692537 calls
memo: fib(30) = 832040 after 59 calls
Why the slow version is slow
fib_slow(30) calls fib_slow(29) and fib_slow(28). But fib_slow(29) also calls fib_slow(28), and each of those calls fib_slow(27), and so on. The same few values are recomputed an enormous number of times: the call count grows about 1.6 times with every step of n. fib_slow(50) would take about 40 billion calls.
There are only 31 different questions here (fib(0) to fib(30)). Memoization stores each answer the first time it's computed, in a memo table indexed by the question. After that, asking again costs one lookup. Every value is computed once, so the work drops from exponential to linear: 59 calls.
When does this work?
DP applies when a problem has two properties:
- Overlapping subproblems: the recursion asks the same smaller questions many times.
- Optimal substructure: the answer to a problem can be built from the answers to smaller versions of it.
The recipe for memoization is always the same: write the plain recursive solution, add a table keyed by the function's arguments, check it at the top of the function, and fill it before returning.
Your turn: a staircase has n steps, and you can climb 1, 2 or 3 steps at a time. Write ways(n), the number of different sequences of moves that reach the top. There's 1 way to climb 0 steps (do nothing), and for example 4 ways to climb 3 (1+1+1, 1+2, 2+1, 3). n goes up to 60, where plain recursion would never finish, so memoize.