These are the notes for C++ episode 38, the third DSA episode. A program asks the same small question millions of times and times out, so we invent dynamic programming (DP): work each small answer out once, write it down, and build bigger answers from it. We find a recurrence for climbing stairs, watch plain recursion explode, fix it with memoization, crash it with a million stairs, fix that with tabulation, shrink the memory to two variables, and then solve coin change, where the obvious greedy answer is wrong. Every program was compiled with g++ -O2 -std=c++17 main.cpp -o main (g++ 13.3, the SyntaxPilot compiler's command) and run; outputs are copied from those runs. The compiler stops a program after 8 seconds and reports Time Limit Exceeded.
The problem: Raju's staircase game
Raju carries chai up 10 stairs to an office every day. Each move he climbs 1 stair or 2, and every day he wants a different way of climbing (1+1+2+..., 2+2+1+...). How many days can he play before he must repeat a way? In other words: how many ways are there to climb n stairs?
Step 1: small cases and the recurrence
When a problem is too big, try tiny cases by hand:
| Stairs | Ways | Count |
|---|---|---|
| 1 | 1 | 1 |
| 2 | 1+1, 2 | 2 |
| 3 | 1+1+1, 1+2, 2+1 | 3 |
| 4 | 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2 | 5 |
1, 2, 3, 5: each number is the two before it added up. Why? Think about the last move. To stand on stair n, Raju either stepped 1 stair from n - 1 or jumped 2 from n - 2. Every way of reaching n is a way of reaching n - 1 plus one stair, or a way of reaching n - 2 plus two stairs, and no way is counted twice. So:
ways(n) = ways(n - 1) + ways(n - 2)
ways(0) = 1, ways(1) = 1 (base cases)
- A recurrence is a rule that builds an answer from smaller answers of the same problem.
- A base case is the smallest answer you know without the rule (
ways(0) = 1: standing still is one way to climb zero stairs). - These are the Fibonacci numbers, shifted by one.
Step 2: plain recursion (and why it explodes)
The recurrence is already a C++ function. We also count how many times it's called:
#include <iostream>
using namespace std;
long long calls = 0;
long long ways(int n) { // ways to climb n stairs
calls++;
if (n <= 1) return 1; // 0 or 1 stair: one way
return ways(n - 1) + ways(n - 2); // last move: 1 stair or 2
}
int main() {
for (int n = 10; n <= 50; n += 10) {
calls = 0;
long long w = ways(n);
cout << n << " stairs: " << w << " ways, "
<< calls << " calls" << endl;
}
return 0;
}
Output:
10 stairs: 89 ways, 177 calls
20 stairs: 10946 ways, 21891 calls
30 stairs: 1346269 ways, 2692537 calls
40 stairs: 165580141 ways, 331160281 calls
Time Limit Exceeded (stopped after 8 seconds)
Ten stairs: 89 ways (89 days of the game). But 40 stairs needs 331 million calls, and 50 stairs never finishes.
Why? Draw what ways(5) does:
ways(5)
/ \
ways(4) ways(3) <- ways(3) is worked out twice
/ \ / \
ways(3) ways(2) ways(2) ways(1) <- ways(2) three times
...
The function has no memory: the same questions are worked out again and again. Each extra stair makes about 1.6 × the calls, so the time grows exponentially, about O(1.6ⁿ). Fifty stairs means about 40 billion calls. But there are only 51 different questions: ways(0) to ways(50). When the same smaller problems come up again and again, they're called overlapping subproblems, and that's the signal for DP.
Step 3: memoization (top-down DP)
Ravi does the same at his stall: when a customer asks "what's 7 cups and 3 samosas?", he works it out once and writes it in a notebook. Next time, he just reads it. In code, the notebook is a vector memo:
- Before working anything out, check the memo. If the answer is there, return it.
- Otherwise, work it out once, and store it in the memo as you return it.
#include <iostream>
#include <vector>
using namespace std;
long long calls = 0;
vector<long long> memo(91, -1); // -1 = not worked out yet
long long ways(int n) {
calls++;
if (n <= 1) return 1;
if (memo[n] != -1) return memo[n]; // already in the notebook
return memo[n] = ways(n - 1) + ways(n - 2); // work out once, save
}
int main() {
for (int n = 10; n <= 90; n += 20) {
calls = 0;
long long w = ways(n);
cout << n << " stairs: " << w << " ways, "
<< calls << " calls" << endl;
}
return 0;
}
Output:
10 stairs: 89 ways, 19 calls
30 stairs: 1346269 ways, 41 calls
50 stairs: 20365011074 ways, 41 calls
70 stairs: 308061521170129 ways, 41 calls
90 stairs: 4660046610375530309 ways, 41 calls
-1means "not worked out yet". No real answer is negative, so it's a safe marker. (If 0 or -1 could be real answers, use a separatevector<bool> done.)memois global, so it keeps its answers between the calls in the loop: 10 stairs needs 19 calls (not 177); 50 stairs then needs only 41, because the answers up to 30 are already saved; 90 stairs is a 19-digit number, still in 41 calls.- Each of the n questions is worked out once, so the time is O(n) instead of O(1.6ⁿ). This is memoization (from memo, a note to yourself), also called top-down DP: start from the big question and let recursion ask for the smaller ones.
return memo[n] = ...;stores and returns in one line: an assignment's value is the value assigned.
Step 4: a million stairs, and a crash
For very big answers, contests ask for the answer modulo 10⁹ + 7 (the remainder after dividing by 1,000,000,007) so it fits in a long long. Same memoized function, a million stairs:
#include <iostream>
#include <vector>
using namespace std;
const long long MOD = 1000000007; // keep the huge answer modulo 10^9 + 7
vector<long long> memo;
long long ways(int n) {
if (n <= 1) return 1;
if (memo[n] != -1) return memo[n];
return memo[n] = (ways(n - 1) + ways(n - 2)) % MOD;
}
int main() {
int n = 1000000; // a million stairs
memo.assign(n + 1, -1);
cout << "ways(" << n << ") = " << ways(n) << endl;
return 0;
}
Output:
Segmentation fault
Why? ways(1000000) calls ways(999999), which calls ways(999998)... a million calls all waiting at once. Each one keeps a frame on the call stack, and the stack is only about 8 MB. It overflows: a stack overflow, which shows up as a segmentation fault. Memoization fixed the time, but not the depth.
Step 5: tabulation (bottom-up DP)
Builders don't start with the top floor. They build the ground floor first, then each floor on the one below. In code: fill a table from the smallest answer upwards with a plain loop. When we reach stair i, both answers below are already filled in. No recursion, no stack limit. This is tabulation, or bottom-up DP:
#include <iostream>
#include <vector>
using namespace std;
const long long MOD = 1000000007;
int main() {
int n = 1000000;
vector<long long> dp(n + 1); // dp[i] = ways to climb i stairs
dp[0] = 1; dp[1] = 1; // base cases
for (int i = 2; i <= n; i++) // bottom floor first
dp[i] = (dp[i - 1] + dp[i - 2]) % MOD;
cout << "dp[10] = " << dp[10] << endl;
cout << "ways(" << n << ") = " << dp[n] << endl;
return 0;
}
Output:
dp[10] = 89
ways(1000000) = 534400663
dp[10] is 89, the same as before, and a million stairs is instant.
Saving space: keep only what you need
Each stair only uses the two stairs below it, so keep two variables and slide them up:
#include <iostream>
using namespace std;
const long long MOD = 1000000007;
int main() {
int n = 1000000;
long long prev2 = 1, prev1 = 1; // ways(i - 2), ways(i - 1)
for (int i = 2; i <= n; i++) {
long long cur = (prev1 + prev2) % MOD;
prev2 = prev1; // slide the window up one stair
prev1 = cur;
}
cout << "ways(" << n << ") = " << prev1 << endl;
return 0;
}
Output:
ways(1000000) = 534400663
Time is still O(n), but memory drops from a million numbers to two: O(1) space.
Top-down or bottom-up?
| Top-down (memoization) | Bottom-up (tabulation) | |
|---|---|---|
| How | recursion + a memo table | a loop + a dp table |
| Starts from | the big question | the base cases |
| Solves | only the subproblems it needs | every entry, in order |
| Easy to write? | yes, straight from the recurrence | you must pick the filling order |
| Deep inputs | can crash (stack overflow) | no recursion, no limit |
| Memory | the whole table | often shrinks to a few variables |
Both give the same answers in the same O(n) time here.
Step 6: coin change, and why greedy fails
Ravi sells chai in sealed flasks: packets of 1, 4 and 6 cups. An order comes in for exactly 8 cups; Raju wants to carry the fewest packets. The obvious way: always take the biggest packet that fits. Always taking the best-looking choice right now is called greedy:
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<int> packs = {6, 4, 1}; // packet sizes, biggest first
int cups = 8, used = 0;
cout << "Greedy:";
for (int p : packs)
while (cups >= p) { // take the biggest packet that fits
cups -= p; used++;
cout << " " << p;
}
cout << endl << used << " packets" << endl;
return 0;
}
Output:
Greedy: 6 1 1
3 packets
Three packets, but 4 + 4 = 8 is two packets. Greedy is wrong: taking the 6 left 2 cups that only 1-cup packets can fill. A choice that looks best now can ruin later choices, so we must try every possible last packet.
The recurrence: think about the last packet
Let best[x] be the fewest packets for exactly x cups. The last packet is 1, 4 or 6 cups:
best[x] = 1 + min( best[x - 1], best[x - 4], best[x - 6] ) (only the packets that fit)
best[0] = 0
For 8 cups: last packet 4 leaves 4 cups, which is 1 packet, so best[8] = 1 + 1 = 2. The best answer is built from the best answers of smaller amounts: that property is called optimal substructure.
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<int> packs = {1, 4, 6};
int target = 8;
const int INF = 1000000; // "can't be made"
vector<int> best(target + 1, INF); // best[x] = fewest packets for x cups
best[0] = 0; // 0 cups: 0 packets
for (int x = 1; x <= target; x++)
for (int p : packs)
if (p <= x && best[x - p] + 1 < best[x])
best[x] = best[x - p] + 1; // last packet: p
for (int x = 0; x <= target; x++)
cout << x << ":" << best[x] << " ";
cout << endl << "Fewest packets for " << target << " cups: " << best[target] << endl;
return 0;
}
Output:
0:0 1:1 2:2 3:3 4:1 5:2 6:1 7:2 8:2
Fewest packets for 8 cups: 2
INF("infinity") is a big number meaning "can't be made (yet)". It must be big enough thatINF + 1still loses everymin, but small enough thatINF + 1doesn't overflow anint.- The table: 4 cups → 1, 5 cups → 2 (4 + 1), 6 cups → 1, 7 → 2 (6 + 1), 8 → 2 (4 + 4).
- Time O(target × k) for k packet sizes; memory O(target).
- This is the classic coin change (minimum coins) problem. With Indian coins 1, 2, 5, 10 greedy happens to work; with "odd" sets like 1, 4, 6 it doesn't, and DP always does.
The DP recipe
| Step | Question to answer | Stairs | Packets |
|---|---|---|---|
| 1. State | What does dp[i] mean, in words? |
ways to climb i stairs | fewest packets for x cups |
| 2. Base case | The smallest answers you know | dp[0] = dp[1] = 1 |
best[0] = 0 |
| 3. Transition | The recurrence: think about the last move | dp[i-1] + dp[i-2] |
1 + min best[x - p] |
| 4. Order | Fill small before big (or memoize) | i = 2, 3, ..., n | x = 1, 2, ..., target |
| 5. Answer | Which entry is the answer? | dp[n] |
best[target] |
When to think of DP: the same smaller problems repeat (overlapping subproblems), and the best answer is built from the best smaller answers (optimal substructure). Words like "how many ways", "minimum/maximum", "can you make" in a problem are strong hints.
Common mistakes
| Mistake | What you see | Fix |
|---|---|---|
Counting ways in an int |
ways(50) = -1109825406 (20 billion doesn't fit; an int holds up to 2,147,483,647) |
long long, or keep answers % MOD |
Checking the memo but never storing: return ways(n-1) + ways(n-2); |
Time Limit Exceeded (nothing is ever saved) |
return memo[n] = ...; |
| Memoized recursion a million deep | Segmentation fault (stack overflow) |
a bottom-up loop |
| Trusting greedy for coin change | 3 packets when 2 is possible |
best[x] = 1 + min(...) over every packet |
vector<long long> dp(n) then dp[n] |
reads past the end: garbage or a crash (dp.at(n) throws vector::_M_range_check) |
size n + 1 for answers 0..n |
| Memo marker that is also a real answer (0 or -1) | the same work is repeated, or a wrong answer | a value that can't be an answer, or a vector<bool> |
INF = INT_MAX, then best[x - p] + 1 |
overflows to a negative number and wins every min |
a big but safe INF like 1,000,000 |
The first one, run for real:
#include <iostream>
using namespace std;
int main() {
int prev2 = 1, prev1 = 1; // int, not long long
for (int i = 2; i <= 50; i++) {
int cur = prev1 + prev2;
prev2 = prev1; prev1 = cur;
}
cout << "ways(50) = " << prev1 << endl;
return 0;
}
Output:
ways(50) = -1109825406
The second one, run for real (the answer is never written into memo):
#include <iostream>
#include <vector>
using namespace std;
vector<long long> memo(91, -1);
long long ways(int n) {
if (n <= 1) return 1;
if (memo[n] != -1) return memo[n];
return ways(n - 1) + ways(n - 2); // forgot: memo[n] = ...
}
int main() {
cout << ways(50) << endl;
return 0;
}
Output:
Time Limit Exceeded (stopped after 8 seconds)
Mini project: how many ways to pay?
Count the ways to pay Rs 10 with coins of 1, 2 and 5 (order doesn't matter: 5 + 2 + 2 + 1 and 1 + 2 + 5 + 2 are the same mix). State: ways[x] = ways to pay x. Putting the coins in the outer loop counts each mix once (an amount is first built with 1s only, then 2s are allowed, then 5s):
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<int> coins = {1, 2, 5};
int target = 10;
vector<long long> ways(target + 1, 0);
ways[0] = 1; // one way to pay 0: no coins
for (int c : coins) // coins in the OUTER loop:
for (int x = c; x <= target; x++) // each mix is counted once
ways[x] += ways[x - c];
cout << "Ways to pay Rs " << target << ": " << ways[target] << endl;
return 0;
}
Output:
Ways to pay Rs 10: 10
If you swap the loops (amounts outside, coins inside), you count orders instead (1 + 2 and 2 + 1 become different), which is the stairs problem again.
Practice
- The stairs, with 1, 2 or 3 stairs at a time, for n = 30.
- Fewest coins for 11 with coins 1, 5 and 7. What does greedy say?
- Can exactly 7 cups be made from packets of 3 and 5? Which amounts up to 12 can?
- House robber: houses in a row hold 20, 50, 30, 10 and 60 rupees. You can't rob two houses side by side. What's the most you can take?
Solutions
Exercise 1: the last move is 1, 2 or 3 stairs.
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n = 30;
vector<long long> dp(n + 1);
dp[0] = 1; dp[1] = 1; dp[2] = 2; // base cases
for (int i = 3; i <= n; i++)
dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]; // last move: 1, 2 or 3 stairs
cout << "ways(" << n << ") = " << dp[n] << endl;
return 0;
}
Output:
ways(30) = 53798080
Exercise 2: last[x] remembers which coin gave the best answer, so we can print the coins too.
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<int> coins = {1, 5, 7};
int target = 11;
const int INF = 1000000;
vector<int> best(target + 1, INF), last(target + 1, -1);
best[0] = 0;
for (int x = 1; x <= target; x++)
for (int c : coins)
if (c <= x && best[x - c] + 1 < best[x]) {
best[x] = best[x - c] + 1;
last[x] = c; // remember which coin we used last
}
cout << "Fewest coins for " << target << ": " << best[target] << " =";
for (int x = target; x > 0; x -= last[x]) cout << " " << last[x];
cout << endl;
return 0;
}
Output:
Fewest coins for 11: 3 = 1 5 5
Greedy would take 7, then 1 + 1 + 1 + 1: 5 coins. DP finds 5 + 5 + 1: 3 coins.
Exercise 3: a vector<bool> DP ("can it be made?"): can[x] is true if some packet p leaves an amount that can be made.
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<int> packs = {3, 5};
int target = 12;
vector<bool> can(target + 1, false);
can[0] = true; // 0 cups: take nothing
for (int x = 1; x <= target; x++)
for (int p : packs)
if (p <= x && can[x - p]) can[x] = true;
for (int x = 0; x <= target; x++)
cout << x << (can[x] ? ":yes " : ":no ");
cout << endl;
return 0;
}
Output:
0:yes 1:no 2:no 3:yes 4:no 5:yes 6:yes 7:no 8:yes 9:yes 10:yes 11:yes 12:yes
7 cups can't be made (nor 1, 2 or 4); from 8 upwards everything can.
Exercise 4: state best[i] = the most from the first i houses. For house i - 1 you either skip it (best[i - 1]) or rob it and skip the one before (best[i - 2] + money[i - 1]).
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
vector<int> money = {20, 50, 30, 10, 60};
int n = money.size();
vector<int> best(n + 1, 0); // best[i] = most from the first i houses
best[1] = money[0];
for (int i = 2; i <= n; i++)
best[i] = max(best[i - 1], // skip house i-1
best[i - 2] + money[i - 1]); // rob house i-1, so skip i-2
cout << "Most you can take: " << best[n] << endl;
return 0;
}
Output:
Most you can take: 110
20 + 30 + 60 = 110.
Quick quiz
Raju can now climb 1, 2 or 3 stairs at a time. What does this print?
dp[0] = 1; dp[1] = 1; dp[2] = 2;
for (int i = 3; i <= 4; i++)
dp[i] = dp[i-1] + dp[i-2] + dp[i-3];
cout << dp[4];
Answer
7. dp[3] = 2 + 1 + 1 = 4, then dp[4] = dp[3] + dp[2] + dp[1] = 4 + 2 + 1 = 7. The full program, run:
#include <iostream>
using namespace std;
int main() {
long long dp[5];
dp[0] = 1; dp[1] = 1; dp[2] = 2;
for (int i = 3; i <= 4; i++)
dp[i] = dp[i-1] + dp[i-2] + dp[i-3];
cout << dp[4] << endl;
return 0;
}
Output:
7
Interview questions
- What is dynamic programming? Solving a problem by combining answers to smaller subproblems, computing each subproblem once and storing it.
- Which two properties make DP work? Overlapping subproblems (the same subproblems repeat) and optimal substructure (an optimal answer is built from optimal answers to subproblems).
- Memoization vs tabulation? Memoization is top-down recursion with a cache; it only solves needed subproblems but can overflow the stack. Tabulation is a bottom-up loop that fills a table in dependency order; no recursion, and the memory can often be reduced.
- Time of naive recursive Fibonacci, and with DP? Exponential, about O(1.6ⁿ) (O(2ⁿ) as a simple bound); O(n) with memoization or tabulation.
- Why can greedy fail on coin change? A locally best choice (the biggest coin) can force worse choices later; with coins 1, 4, 6 and amount 8 greedy uses 3 coins, DP finds 2.
- How do you reduce DP memory? If
dp[i]only depends on a few previous entries, keep only those (two variables for stairs/Fibonacci: O(1) space). - How do you print the actual solution, not just its value? Store the choice made at each state (like
last[x]) and follow it back from the answer. - Classic DP problems to know: climbing stairs, coin change (min coins and number of ways), house robber, 0/1 knapsack, longest common subsequence, longest increasing subsequence, edit distance.
Glossary
| Term | Meaning, with an example |
|---|---|
| dynamic programming (DP) | Solve each smaller problem once, save the answer, build bigger answers from it. |
| subproblem | A smaller version of the same problem: ways(8) inside ways(10). |
| recurrence | A rule that builds an answer from smaller answers: ways(n) = ways(n-1) + ways(n-2). |
| base case | An answer known without the rule: ways(0) = ways(1) = 1. |
| state | What one table entry means, in words: dp[i] = ways to climb i stairs. |
| transition | The recurrence used to fill a state from earlier states. |
| overlapping subproblems | The same subproblems come up again and again (ways(3) many times). |
| optimal substructure | The best answer is built from best answers of subproblems: best[8] from best[4]. |
| exponential time | Each step up multiplies the work, like O(1.6ⁿ): 50 stairs = 40 billion calls. |
| memoization (top-down DP) | Recursion that checks a saved-answers table (memo) first and saves every new answer. |
| memo | The table of saved answers; -1 = not worked out yet. |
| tabulation (bottom-up DP) | A loop that fills the table from the base cases upwards. |
dp table |
The vector of answers in tabulation: dp[0] ... dp[n]. |
| call stack | The memory where each waiting function call keeps its frame (about 8 MB). |
| stack overflow | Too many calls waiting at once; the stack runs out and the program crashes (segmentation fault). |
modulo (%) |
The remainder after dividing; answers are kept % 1000000007 so they fit. |
MOD = 10⁹ + 7 |
A big prime used in contests to keep huge answers small. |
| greedy | Always take the choice that looks best right now; fast, but can be wrong. |
| coin change | Fewest coins (or number of ways) to make an amount from given coins. |
INF |
A big stand-in for "infinity": "can't be made yet". |
| O(1) space | Memory that doesn't grow with n: two variables. |
| integer overflow | A result too big for its type wraps around: ways(50) in an int printed a negative number. |
Summary
- Think about the last move to find a recurrence; add base cases.
- Plain recursion repeats the same overlapping subproblems: exponential time, Time Limit Exceeded.
- Memoization (top-down): check the memo, compute once, store. O(n).
- Very deep recursion overflows the stack: use tabulation (bottom-up loop); often only the last few values are needed (O(1) space).
- Greedy can be wrong; DP tries every last choice: coin change in O(target × k).
- Recipe: state, base case, transition, order, answer.
- Next episode: competitive programming patterns (prefix sums, fast I/O, two pointers, sliding window).