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 task
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.
Challenge 2
Letters are encoded as numbers: A is 1, B is 2, ..., Z is 26. Write long long decodings(const std::string& s): how many ways a string of digits can be read back as letters. "226" is 3 (2 2 6, 22 6, 2 26), and a 0 can only be read as part of 10 or 20. Build it up from the end of the string: the ways from position i depend on the ways from i + 1 and i + 2.
Challenge 3
Starting from n, each move either subtracts 1, halves the number (if it's even) or divides it by 3 (if it's a multiple of 3). Write int steps_to_one(int n), the fewest moves to reach 1, for n up to 1,000,000. Greedy division doesn't always win (10 takes 3 moves: 10, 9, 3, 1), so fill a table from 1 upward.