Dynamic Programming — classic problems
Seven rudimentary DP problems worked end to end, each as top-down recursion + memoization — Fibonacci, climbing stairs, max subarray (Kadane), house robber, coin change (min and count), 0/1 knapsack, and longest increasing subsequence. Each gives the state, recurrence, base cases, and clean contest C++.
1. Fibonacci — the 'hello world' of DP
Problem: compute the n-th Fibonacci number, F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2).
Why it's the first DP: it shows overlapping subproblems in their purest form. Naïve recursion is O(2ⁿ); adding a memo makes it O(n) while keeping the natural recursive shape.
State: fib(n) = F(n). Transition: fib(n) = fib(n-1) + fib(n-2). Base: fib(0)=0, fib(1)=1.
Top-down memoization:
long long memo[100005];
bool seen[100005];
long long fib(int n) {
if (n < 2) return n; // base case
if (seen[n]) return memo[n]; // reuse a solved subproblem
seen[n] = true;
return memo[n] = fib(n - 1) + fib(n - 2);
}The seen[] flag marks "already computed" so each n is solved exactly once; every later call is an O(1) cache hit.
Contest note: Fibonacci grows fast — F(93) overflows 64-bit. For large n, problems ask for the answer modulo 10⁹+7; take the mod at the return: return memo[n] = (fib(n-1) + fib(n-2)) % MOD;.
2. Climbing stairs — counting paths
Problem: you climb a staircase of n steps, taking either 1 or 2 steps at a time. How many distinct ways to reach the top?
State: ways(n) = number of ways to cover n remaining steps. Transition: the next move is a 1-step or a 2-step, so ways(n) = ways(n-1) + ways(n-2). Base: ways(0)=1 (one way: stop), ways(1)=1.
It's literally Fibonacci shifted — but the modelling is the lesson: "ways to a state = sum of ways to the states you can move to."
long long memo[100005];
bool seen[100005];
long long climb(int n) {
if (n <= 1) return 1; // base: 0 or 1 step left
if (seen[n]) return memo[n];
seen[n] = true;
return memo[n] = climb(n - 1) + climb(n - 2);
}Generalisation worth knowing: if you may take steps whose sizes are in a set S (say 1, 2, 3), then climb(n) = Σ climb(n - s) for each s ∈ S with n - s ≥ 0. This is the gateway to coin-change counting below.
3. Maximum subarray sum — Kadane's algorithm
Problem: given an array (with possible negatives), find the maximum sum of any contiguous non-empty subarray.
State: best(i) = the maximum subarray sum that ends exactly at index i. Transition: the best subarray ending at i either starts fresh at i, or extends the best one ending at i-1:
The final answer is max over all i of best(i) — the optimal subarray ends somewhere. Pinning the recursion to "ends at i" is the trick that makes each call O(1).
int n;
vector<int> a;
long long memo[100005];
bool seen[100005];
long long best(int i) {
if (i == 0) return a[0]; // base: only a[0] ends here
if (seen[i]) return memo[i];
seen[i] = true;
return memo[i] = max((long long)a[i], best(i - 1) + a[i]);
}
// answer: long long ans = a[0]; for (int i = 0; i < n; i++) ans = max(ans, best(i));Watch out: the answer is the max over all best(i), not best(n-1). And the base seeds with a[0] (never 0), so an all-negative array like [-3,-1,-2] correctly returns -1 (the least-negative element). Note the recursion runs to depth n — for n near 10⁶, prefer the iterative one-liner to avoid stack overflow.
4. House robber — the pick-or-skip 1D DP
Problem: houses in a row hold a[0..n-1] cash. You can't rob two adjacent houses. Maximise the total robbed.
State: rob(i) = the most you can rob from houses i..n-1. Transition: at house i you either skip it (rob(i+1)) or rob it (a[i] + rob(i+2), since i+1 becomes off-limits):
Base: rob(i) = 0 for i ≥ n (no houses left).
int n;
vector<int> a;
int memo[100005]; // init to -1
int rob(int i) {
if (i >= n) return 0; // base
if (memo[i] != -1) return memo[i];
int take = a[i] + rob(i + 2); // rob i, skip i+1
int skip = rob(i + 1); // skip i
return memo[i] = max(take, skip);
}
// answer: rob(0)This is the prototype for a huge class of "select a subset of a sequence under an adjacency/spacing constraint" problems. Recognising the max(skip, take + jump-ahead) shape instantly saves real time in contests.
5. Coin change — minimum coins and number of ways
Two distinct DPs share the same setup: coin denominations c[] (unlimited supply) and a target amount.
(a) Minimum number of coins. solveMin(x) = fewest coins summing to x. Try each coin as the last coin used.
const int INF = 1e9;
vector<int> coins;
int memo[10005]; // init to -2 (uncomputed); 0 is a valid answer so don't use -1... use -2
int solveMin(int x) {
if (x == 0) return 0; // base
if (memo[x] != -2) return memo[x];
int best = INF;
for (int c : coins)
if (c <= x) best = min(best, solveMin(x - c) + 1);
return memo[x] = best;
}
// answer: solveMin(amount) >= INF ? -1 : solveMin(amount)(b) Number of combinations (order doesn't matter). Add a coin index to the state so each combination is counted once: ways(i, x) = combinations using coins i..m-1 summing to x.
vector<int> coins;
int m;
long long memo2[105][10005]; // init to -1
long long ways(int i, int x) {
if (x == 0) return 1; // amount made
if (i == m || x < 0) return 0;
if (memo2[i][x] != -1) return memo2[i][x];
long long skip = ways(i + 1, x); // retire coin i
long long take = (coins[i] <= x) ? ways(i, x - coins[i]) : 0; // reuse coin i
return memo2[i][x] = skip + take;
}The crucial subtlety: the coin index i in the state is what counts combinations rather than permutations. The take branch stays at i (the coin is reusable); the skip branch advances to i+1 (the coin is retired). Drop the index and you'd count 1+2 and 2+1 separately.
6. 0/1 knapsack — the optimisation workhorse
Problem: n items, item i has weight w[i] and value v[i]. Choose a subset with total weight ≤ W maximising total value. Each item used at most once.
State: solve(i, cap) = best value using items i..n-1 with remaining capacity cap. Transition: skip item i, or take it (if it fits) and move on to the next item:
Base: solve(n, cap) = 0 and solve(i, 0) = 0.
int n, W;
vector<int> w, v;
int memo[1005][1005]; // init to -1; states (i, cap)
int solve(int i, int cap) {
if (i == n || cap == 0) return 0; // base
int& m = memo[i][cap];
if (m != -1) return m;
int skip = solve(i + 1, cap);
int take = (w[i] <= cap) ? v[i] + solve(i + 1, cap - w[i]) : 0;
return m = max(skip, take);
}
// answer: solve(0, W)0/1 vs. unbounded — the one-line difference: the take branch recurses on i+1, so each item is used once. If items could be reused without limit (unbounded knapsack / coin change), the take branch would recurse on i instead. That single index choice is the recursive analog of the famous bottom-up loop-direction trick — much easier to see and impossible to get backwards.
7. Longest increasing subsequence (LIS)
Problem: find the length of the longest strictly increasing subsequence (not necessarily contiguous).
State: endAt(i) = length of the longest increasing subsequence ending at index i. Transition: extend the best earlier chain whose last element is smaller:
O(n²) top-down — learn this one first:
int n;
vector<int> a;
int memo[5005]; // init to -1
int endAt(int i) {
if (memo[i] != -1) return memo[i];
int best = 1; // the element alone is length 1
for (int j = 0; j < i; j++)
if (a[j] < a[i])
best = max(best, endAt(j) + 1); // extend a shorter chain
return memo[i] = best;
}
// answer = max over all i of endAt(i)O(n log n) version — know it exists (not a DP). Maintain tails[k] = smallest possible tail of an increasing subsequence of length k+1, and binary-search each element's slot with lower_bound. It's a greedy/patience-sorting technique rather than recursive DP, but it's what you submit when n reaches ~10⁵–10⁶:
int lisFast(const vector<int>& a) {
vector<int> tails;
for (int x : a) {
auto it = lower_bound(tails.begin(), tails.end(), x); // strictly increasing
if (it == tails.end()) tails.push_back(x);
else *it = x;
}
return tails.size();
}Use upper_bound instead of lower_bound if the subsequence may be non-decreasing (ties allowed).