These are the notes for C++ Coding Questions, episode 29, placement practice for people who finished the SyntaxPilot C++ course. Dynamic programming (DP) is the topic candidates fear most, and it is one simple idea: never solve the same smaller problem twice. Three classic questions: climbing stairs (recursion vs memoization vs a table), minimum coins (where greedy is wrong, and an INT_MAX + 1 overflow), and the longest common subsequence (a 2D table).
Each question follows the same steps: read the problem, think out loud, the obvious attempt, a real failure, why, the fix, every test case, and the cost.
Every program was compiled with g++ -Wall -O2 -std=c++17 main.cpp -o main (g++ 13.3, Linux x86-64), the SyntaxPilot compiler's C++ command with warnings on, and every output below is real. Timings (ms) change from machine to machine and run to run; the call counts do not.
Real-life pictures
| In real life | In C++ |
|---|---|
| Temple steps, 1 or 2 at a time: your last move was 1 step or 2 | the recurrence ways(n) = ways(n-1) + ways(n-2) |
| Asking around and getting the same small counts worked out again and again | overlapping subproblems: exponential recursion |
| Writing each answer on the wall once, then reusing it | memoization / a bottom-up table |
| Rupee coins 10, 5, 2, 1: biggest first works | greedy is right for some coin systems |
| Arcade tokens 5, 4, 1: biggest first pays 8 with 4 tokens, 4 + 4 needs 2 | greedy is wrong in general: try every coin |
| Two radio playlists: the longest list of songs both played, in order | the longest common subsequence |
| Grabbing the first matching song you see | greedy matching: an early match blocks better ones |
What dynamic programming is
A problem fits DP when it has:
- Optimal substructure: the answer is built from answers to smaller versions of the same problem (a recurrence).
- Overlapping subproblems: those smaller versions are needed again and again.
Two ways to write it:
| Style | How | Also called |
|---|---|---|
| Top-down | the recursion, plus a cache of answers already worked out | memoization |
| Bottom-up | fill a table from the smallest subproblem up, with loops | tabulation |
A recipe that works for every question in this episode: (1) say what dp[x] means in words, (2) find the recurrence by asking "what was the last move / last coin / last character?", (3) the base cases, (4) the order to fill the table, (5) where the answer is.
Q1: Climbing stairs
Problem. You climb a staircase 1 or 2 steps at a time. In how many different ways can you reach step n?
n = 3 → 3 (1+1+1, 1+2, 2+1)
n = 5 → 8
n = 45 → 1836311903
Think out loud. Your last move onto step n was either 1 step (from n-1) or 2 steps (from n-2), and those two groups don't overlap. So ways(n) = ways(n-1) + ways(n-2), with ways(0) = ways(1) = 1 (standing still at the bottom is one way). Edge cases: n = 0, n = 1, and big n.
The obvious attempt: plain recursion
#include <iostream>
#include <chrono>
using namespace std;
long long calls = 0;
long long ways(int n) { // ways to climb n steps
calls++;
if (n <= 1) return 1; // 0 or 1 step: one way
return ways(n - 1) + ways(n - 2); // last move: 1 step or 2
}
int main() {
cout << "ways(3) = " << ways(3) << ", ways(5) = " << ways(5) << "\n";
for (int n : {30, 35, 40, 45}) {
calls = 0;
auto t0 = chrono::steady_clock::now();
long long w = ways(n);
auto t1 = chrono::steady_clock::now();
auto ms = chrono::duration_cast<chrono::milliseconds>(t1 - t0);
cout << "n = " << n << ": " << w << " ways, " << calls
<< " calls, " << ms.count() << " ms\n";
}
return 0;
}
Real output (one run):
ways(3) = 3, ways(5) = 8
n = 30: 1346269 ways, 2692537 calls, 1 ms
n = 35: 14930352 ways, 29860703 calls, 13 ms
n = 40: 165580141 ways, 331160281 calls, 157 ms
n = 45: 1836311903 ways, 3672623805 calls, 1648 ms
Correct answers, but 3.6 billion calls for n = 45, and every 5 more steps cost about 11 times more.
Why
ways(5) calls ways(4) and ways(3); ways(4) calls ways(3) again; ways(3) is solved twice, ways(2) three times, and so on. The number of calls is 2 · ways(n) − 1, which grows like 1.618^n: exponential, roughly O(2^n). n = 50 would need over 40 billion calls.
Fix 1: memoization (top-down)
#include <iostream>
#include <vector>
using namespace std;
long long calls = 0;
vector<long long> memo; // memo[n] = answer, -1 = not known
long long ways(int n) {
calls++;
if (n <= 1) return 1;
if (memo[n] != -1) return memo[n]; // solved before: reuse it
return memo[n] = ways(n - 1) + ways(n - 2);
}
int main() {
for (int n : {45, 90}) {
memo.assign(n + 1, -1);
calls = 0;
cout << "n = " << n << ": " << ways(n) << " ways, "
<< calls << " calls\n";
}
return 0;
}
n = 45: 1836311903 ways, 89 calls
n = 90: 4660046610375530309 ways, 179 calls
Each step is solved once: O(n) time, O(n) space (the memo and the recursion stack). ways(90) still fits in a long long (max about 9.22 × 10^18); ways(92) would not.
Fix 2: bottom-up table with two variables
#include <iostream>
using namespace std;
long long ways(int n) { // bottom-up: smallest first
long long prev2 = 1, prev1 = 1; // ways(0), ways(1)
for (int i = 2; i <= n; i++) {
long long cur = prev1 + prev2; // ways(i-1) + ways(i-2)
prev2 = prev1;
prev1 = cur;
}
return prev1;
}
int main() {
for (int n : {0, 1, 2, 3, 5, 45, 90})
cout << "ways(" << n << ") = " << ways(n) << "\n";
return 0;
}
ways(0) = 1
ways(1) = 1
ways(2) = 2
ways(3) = 3
ways(5) = 8
ways(45) = 1836311903
ways(90) = 4660046610375530309
O(n) time, O(1) space, no recursion (so no stack overflow for big n). (These are the Fibonacci numbers shifted by one.)
Q2: Minimum coins (coin change)
Problem. Given coin values (each usable any number of times) and an amount, return the fewest coins that make the amount, or -1 if it is impossible.
{5, 4, 1}, 8 → 2 (4 + 4)
{5, 4}, 3 → -1 (impossible)
{5, 4}, 13 → 3 (5 + 4 + 4)
Think out loud. Greedy means: always take the choice that looks best right now, and never go back. Biggest coin first works for Indian rupee coins. Does it always work? Edge cases: impossible amounts, amount 0, coin systems where greedy fails.
The obvious attempt: greedy
#include <iostream>
#include <vector>
using namespace std;
int greedyCoins(const vector<int>& coins, int amount) { // big to small
int count = 0;
for (int c : coins)
while (amount >= c) { amount -= c; count++; } // biggest first
return amount == 0 ? count : -1;
}
int main() {
vector<int> rupees = {10, 5, 2, 1};
cout << "rupees, 18: " << greedyCoins(rupees, 18) << " coins\n";
vector<int> tokens = {5, 4, 1}; // arcade tokens
cout << "tokens, 8: " << greedyCoins(tokens, 8) << " coins\n";
return 0;
}
rupees, 18: 4 coins
tokens, 8: 4 coins
Rupees: right (10 + 5 + 2 + 1). Tokens: wrong, 5 + 1 + 1 + 1 = 4 tokens, but 4 + 4 = 2.
Why, and the recurrence
Taking 5 first leaves 3, which needs three 1s, and greedy can never undo the 5. Instead ask: what was the last coin? If it was c, the rest is the best way to pay a - c:
dp[a] = min over every coin c ≤ a of dp[a - c] + 1 dp[0] = 0
a: 0 1 2 3 4 5 6 7 8
dp: 0 1 2 3 1 1 2 3 2 (coins {5, 4, 1})
The DP, first try: INT_MAX as "impossible"
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
int minCoins(const vector<int>& coins, int amount) {
vector<int> dp(amount + 1, INT_MAX); // INT_MAX = "can't make it"
dp[0] = 0;
for (int a = 1; a <= amount; a++)
for (int c : coins)
if (c <= a) dp[a] = min(dp[a], dp[a - c] + 1);
return dp[amount] == INT_MAX ? -1 : dp[amount];
}
int main() {
cout << "tokens {5, 4, 1}, 8: " << minCoins({5, 4, 1}, 8) << "\n";
cout << "tokens {5, 4}, 3: " << minCoins({5, 4}, 3) << "\n";
cout << "tokens {5, 4}, 7: " << minCoins({5, 4}, 7) << "\n";
return 0;
}
tokens {5, 4, 1}, 8: 2
tokens {5, 4}, 3: -1
tokens {5, 4}, 7: -2147483648
Why -2147483648? With coins {5, 4}, dp[2] stays INT_MAX (2 can't be made). For a = 7, the coin 5 reads dp[2] + 1 = INT_MAX + 1, which does not fit in an int: signed integer overflow, undefined behaviour. Here it wrapped to INT_MIN, and min happily picked it. Compiled with -fsanitize=undefined, the program reports it: runtime error: signed integer overflow: 2147483647 + 1 cannot be represented in type 'int'.
The fix: amount + 1 as infinity
You never need more than amount coins (that is, all 1s), so amount + 1 is safely "too many", and adding 1 to it cannot overflow.
#include <iostream>
#include <vector>
using namespace std;
int minCoins(const vector<int>& coins, int amount) {
const int INF = amount + 1; // more coins than ever needed
vector<int> dp(amount + 1, INF); // dp[a] = fewest coins for a
dp[0] = 0;
for (int a = 1; a <= amount; a++)
for (int c : coins)
if (c <= a) dp[a] = min(dp[a], dp[a - c] + 1);
return dp[amount] >= INF ? -1 : dp[amount];
}
int main() {
cout << "tokens {5, 4, 1}, 8: " << minCoins({5, 4, 1}, 8) << "\n";
cout << "tokens {5, 4}, 3: " << minCoins({5, 4}, 3) << "\n";
cout << "tokens {5, 4}, 7: " << minCoins({5, 4}, 7) << "\n";
cout << "tokens {5, 4}, 13: " << minCoins({5, 4}, 13) << "\n";
cout << "rupees, 0: " << minCoins({10, 5, 2, 1}, 0) << "\n";
cout << "rupees, 18: " << minCoins({10, 5, 2, 1}, 18) << "\n";
return 0;
}
tokens {5, 4, 1}, 8: 2
tokens {5, 4}, 3: -1
tokens {5, 4}, 7: -1
tokens {5, 4}, 13: 3
rupees, 0: 0
rupees, 18: 4
(Another fix: skip dp[a - c] when it is INT_MAX.) Cost: O(amount × number of coins) time, O(amount) space.
Q3: Longest common subsequence (LCS)
Problem. Given two strings, return the length of their longest common subsequence. A subsequence is some items of a sequence kept in their order, with gaps allowed ("ACD" is a subsequence of "ABCD"). A substring has no gaps.
"ABCD" vs "ACD" → 3 (ACD)
"ABCBDAB" vs "BDCABA" → 4 (BCBA, among others)
"ABC" vs "XYZ" → 0
Think of two radio stations' playlists: the longest list of songs both played in the same order. The same table powers diff, version control and DNA comparison.
The obvious attempt: greedy matching
#include <iostream>
#include <string>
using namespace std;
int greedyCommon(const string& a, const string& b) {
int count = 0;
size_t j = 0;
for (char song : a) { // each song of station a, in order
size_t pos = b.find(song, j); // the next time b plays it
if (pos != string::npos) { count++; j = pos + 1; }
}
return count;
}
int main() {
cout << greedyCommon("ABCD", "ACD") << "\n"; // expect 3
cout << greedyCommon("ABCBDAB", "BDCABA") << "\n"; // expect 4
return 0;
}
3
3
Why. For the playlists, greedy matched a's first song A with b's A at position 3, jumping past B, D, C; it then found only B and A ("ABA", 3). An early match can block better ones.
The table
dp[i][j] = the LCS length of the first i characters of a and the first j characters of b. Row 0 and column 0 are the empty prefix (LCS 0). Look at the last characters:
a[i-1] == b[j-1] → dp[i][j] = dp[i-1][j-1] + 1 (same: take it)
otherwise → dp[i][j] = max(dp[i-1][j], dp[i][j-1]) (skip one of them)
The answer is dp[n][m], the bottom-right corner. To read the subsequence itself, walk back from the corner: on a match go diagonally and record the character, otherwise move to the bigger neighbour.
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
string lcs(const string& a, const string& b) {
int n = a.size(), m = b.size();
vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
if (a[i - 1] == b[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
string out; // walk back to read the songs
for (int i = n, j = m; i > 0 && j > 0; ) {
if (a[i - 1] == b[j - 1]) { out += a[i - 1]; i--; j--; }
else if (dp[i - 1][j] >= dp[i][j - 1]) i--;
else j--;
}
reverse(out.begin(), out.end());
return out;
}
void test(const string& a, const string& b) {
string s = lcs(a, b);
cout << a << " vs " << b << ": " << s.size() << " (" << s << ")\n";
}
int main() {
test("ABCD", "ACD");
test("ABCBDAB", "BDCABA");
test("ABC", "XYZ");
test("", "ABC");
test("RAHUL", "RAHUL");
return 0;
}
ABCD vs ACD: 3 (ACD)
ABCBDAB vs BDCABA: 4 (BCBA)
ABC vs XYZ: 0 ()
vs ABC: 0 ()
RAHUL vs RAHUL: 5 (RAHUL)
Cost: O(n × m) time and space (an 8 × 7 table for the playlists). If you only need the length, keep two rows: O(min(n, m)) space.
Cost summary
| Question | Obvious attempt | Result | DP fix | Time | Space |
|---|---|---|---|---|---|
| Climbing stairs | plain recursion | 3,672,623,805 calls for n = 45 | memo / two variables | O(n) | O(n) / O(1) |
| Minimum coins | greedy biggest-first | 4 tokens for 8 (answer 2) | dp[a] = min(dp[a-c] + 1) |
O(amount × coins) | O(amount) |
(DP with INT_MAX) |
INT_MAX + 1 |
-2147483648 | INF = amount + 1 |
||
| LCS | greedy first match | 3 (answer 4) | dp[i][j] table |
O(n × m) | O(n × m) |
Common mistakes (and the real results)
| Mistake | What you see | Why | Fix |
|---|---|---|---|
plain recursion for ways(45) |
correct, 3,672,623,805 calls | overlapping subproblems | memo or a bottom-up table |
| memo filled with 0 as "unknown" when 0 is a real answer | repeated work, or wrong answers | can't tell "unknown" from 0 | use -1 (or optional) |
int for ways(n) |
negative numbers from n = 46 |
overflow past 2,147,483,647 | long long (up to n = 91) |
| greedy biggest coin first | 4 tokens instead of 2 | never undoes a choice | try every coin as the last one |
INT_MAX as infinity, then + 1 |
-2147483648 |
signed overflow (UB) | INF = amount + 1, or skip INF entries |
| greedy first match for LCS | 3 instead of 4 | an early match blocks better ones | the dp[i][j] table |
table of size n × m, loops from 0 |
a[i - 1] reads a[-1] |
no row for the empty prefix | size (n+1) × (m+1), loops from 1 |
| confusing subsequence with substring | wrong answers | substrings have no gaps | LCS allows gaps |
Mini project: a tiny diff of two to-do lists
LCS on lines instead of characters: the lines in the LCS are kept; the others were removed (-) or added (+). This is how git diff works at heart.
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
// A tiny "diff": which lines were kept, removed (-) or added (+)?
int main() {
vector<string> before = {"buy milk", "pay rent", "call Priya", "book train", "gym"};
vector<string> after = {"pay rent", "call Priya", "buy vegetables", "gym", "read"};
int n = before.size(), m = after.size();
vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
dp[i][j] = before[i - 1] == after[j - 1] ? dp[i - 1][j - 1] + 1
: max(dp[i - 1][j], dp[i][j - 1]);
vector<string> out; // walk back from the corner
int i = n, j = m;
while (i > 0 || j > 0) {
if (i > 0 && j > 0 && before[i - 1] == after[j - 1]) { out.push_back(" " + before[i - 1]); i--; j--; }
else if (j > 0 && (i == 0 || dp[i][j - 1] >= dp[i - 1][j])) { out.push_back("+ " + after[j - 1]); j--; }
else { out.push_back("- " + before[i - 1]); i--; }
}
reverse(out.begin(), out.end());
for (const string& line : out) cout << line << "\n";
cout << "kept " << dp[n][m] << " of " << n << " lines\n";
return 0;
}
Real output:
- buy milk
pay rent
call Priya
- book train
+ buy vegetables
gym
+ read
kept 3 of 5 lines
Practice questions (with solutions)
1. Your turn: stairs with 1, 2 or 3 steps. n = 3 → 4, n = 4 → 7, n = 30 → ?
Solution
The last move was 1, 2 or 3 steps: ways(n) = ways(n-1) + ways(n-2) + ways(n-3), with ways(0) = 1, ways(1) = 1, ways(2) = 2. Keep three variables.
#include <iostream>
using namespace std;
long long ways3(int n) { // 1, 2 or 3 steps at a time
if (n == 0) return 1;
long long a = 1, b = 1, c = 2; // ways(0), ways(1), ways(2)
if (n == 1) return b;
for (int i = 3; i <= n; i++) {
long long d = a + b + c; // last move: 3, 2 or 1 steps
a = b; b = c; c = d;
}
return c;
}
int main() {
for (int n : {0, 1, 2, 3, 4, 5, 30})
cout << "ways3(" << n << ") = " << ways3(n) << "\n";
return 0;
}
ways3(0) = 1
ways3(1) = 1
ways3(2) = 2
ways3(3) = 4
ways3(4) = 7
ways3(5) = 13
ways3(30) = 53798080
O(n) time, O(1) space.
2. Count the WAYS to make an amount (coin change II): how many combinations of coins make the amount?
Solution
ways[a] += ways[a - c], with the coins in the outer loop so each combination is counted once (5 = 1+2+2 and 2+1+2 are the same). With the amount loop outside, you would count orderings instead.
#include <iostream>
#include <vector>
using namespace std;
long long countWays(const vector<int>& coins, int amount) {
vector<long long> ways(amount + 1, 0);
ways[0] = 1; // one way to pay 0: no coins
for (int c : coins) // coins OUTSIDE: combinations
for (int a = c; a <= amount; a++)
ways[a] += ways[a - c];
return ways[amount];
}
int main() {
cout << countWays({1, 2, 5}, 5) << "\n"; // 4
cout << countWays({2}, 3) << "\n"; // 0
cout << countWays({1, 2, 5, 10}, 100) << "\n";
return 0;
}
4
0
2156
3. Print the coins used, not just the count.
Solution
Remember which coin gave each dp[a], then follow it back from amount.
#include <iostream>
#include <vector>
using namespace std;
vector<int> coinsUsed(const vector<int>& coins, int amount) {
const int INF = amount + 1;
vector<int> dp(amount + 1, INF), last(amount + 1, -1); // last[a] = coin used
dp[0] = 0;
for (int a = 1; a <= amount; a++)
for (int c : coins)
if (c <= a && dp[a - c] + 1 < dp[a]) { dp[a] = dp[a - c] + 1; last[a] = c; }
vector<int> used;
if (dp[amount] >= INF) return used; // impossible: empty
for (int a = amount; a > 0; a -= last[a]) used.push_back(last[a]);
return used;
}
int main() {
for (int c : coinsUsed({5, 4, 1}, 8)) cout << c << " ";
cout << "\n";
for (int c : coinsUsed({5, 4}, 13)) cout << c << " ";
cout << "\n";
cout << coinsUsed({5, 4}, 7).size() << " coins (impossible)\n";
return 0;
}
4 4
5 4 4
0 coins (impossible)
4. LCS, then the edit distance. The fewest single-character inserts, deletes or replacements to turn a into b.
Solution
Same table shape as LCS. Row 0 and column 0: turning a prefix into the empty string costs its length.
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int editDistance(const string& a, const string& b) {
int n = a.size(), m = b.size();
vector<vector<int>> dp(n + 1, vector<int>(m + 1));
for (int i = 0; i <= n; i++) dp[i][0] = i; // delete everything
for (int j = 0; j <= m; j++) dp[0][j] = j; // insert everything
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
if (a[i - 1] == b[j - 1]) dp[i][j] = dp[i - 1][j - 1];
else dp[i][j] = 1 + min({dp[i - 1][j], // delete
dp[i][j - 1], // insert
dp[i - 1][j - 1]}); // replace
return dp[n][m];
}
int main() {
cout << editDistance("chai", "chair") << "\n"; // 1
cout << editDistance("samosa", "mimosa") << "\n"; // 2
cout << editDistance("", "abc") << "\n"; // 3
return 0;
}
1
2
3
Quick quiz
1. What does this print? (the episode quiz)
vector<int> dp(7, 99); // coins {1, 3, 4}
dp[0] = 0;
for (int a = 1; a <= 6; a++)
for (int c : {1, 3, 4})
if (c <= a) dp[a] = min(dp[a], dp[a - c] + 1);
cout << dp[6];
(A) 1 (B) 2 (C) 3 (D) 4
Answer
(B) 2: 3 + 3. Greedy would take 4 + 1 + 1 = 3 coins. The table is 0 1 2 1 1 2 2.
2. What is the difference between memoization and tabulation?
Answer
Memoization is top-down: the recursion plus a cache, solving only the subproblems it reaches. Tabulation is bottom-up: loops fill the table from the base cases, with no recursion, and often allow keeping only the last few rows (less memory).
3. How many calls does plain recursive ways(10) make?
Answer
2 · ways(10) − 1 = 2 · 89 − 1 = 177. (Check: ways(30) made 2,692,537 = 2 · 1,346,269 − 1.)
4. LCS of "AXBY" and "XAYB"?
Answer
2 (for example "XB", "AB", "XY" or "AY"). There can be several LCSs of the same length.
Interview questions
- What is dynamic programming? Solving a problem by combining answers to overlapping subproblems, each solved once and stored.
- What two properties make a problem a DP problem? Optimal substructure and overlapping subproblems.
- Memoization vs tabulation? Top-down recursion with a cache vs bottom-up loops over a table.
- Why is plain recursive Fibonacci slow? It recomputes the same values: about 1.618^n calls, exponential.
- How do you find a recurrence? Define
dp[x]in words, then ask what the last step/choice was and how the rest is a smaller instance. - When does greedy work for coin change? For "canonical" coin systems like 1, 2, 5, 10; not in general (5, 4, 1 for 8). DP is always correct.
- Why not use
INT_MAXas infinity?INT_MAX + 1overflows (UB). Use a value bigger than any real answer but safe to add to, likeamount + 1, or skip infinite entries. - Time and space of coin change? O(amount × coins) and O(amount).
- Subsequence vs substring? A subsequence keeps order but allows gaps; a substring is contiguous.
- LCS recurrence? Match:
dp[i-1][j-1] + 1; otherwisemax(dp[i-1][j], dp[i][j-1]). - How do you reconstruct the LCS itself? Walk back from
dp[n][m], going diagonally on matches. - How do you reduce LCS memory? Each row needs only the previous row: two rows, O(min(n, m)) space (for the length only).
- What is the edit distance? The minimum inserts, deletes and replacements to turn one string into another; a DP on the same
(n+1) × (m+1)table.
Glossary
| Term | Meaning | Example |
|---|---|---|
| Dynamic programming (DP) | Solving each overlapping subproblem once and reusing its answer | climbing stairs |
| Subproblem | A smaller version of the same question | ways(3) inside ways(5) |
| Recurrence | A formula that builds an answer from smaller answers | ways(n) = ways(n-1) + ways(n-2) |
| Base case | The smallest answers, known directly | ways(0) = ways(1) = 1 |
| Overlapping subproblems | The same subproblem is needed many times | ways(3) solved twice |
| Optimal substructure | The best answer is built from best answers to subproblems | dp[a] = dp[a - c] + 1 |
| Exponential time | Work that multiplies with each step of n, like O(2^n) | 3.6 billion calls |
| Memoization | Top-down: save each answer the first time, look it up after | memo[n] |
| Tabulation (bottom-up) | Fill a table from the base cases up, with loops | two variables |
| Memo | The cache of saved answers | vector<long long> memo |
| Greedy algorithm | Always takes the best-looking choice now, never goes back | biggest coin first |
| Coin change | The fewest coins (or number of ways) to make an amount | {5, 4, 1}, 8 → 2 |
INT_MAX |
The largest int, 2147483647 |
<climits> |
| Signed integer overflow | A result too big for a signed type: undefined behaviour | INT_MAX + 1 |
| Infinity (sentinel) | A value meaning "impossible", bigger than any real answer | INF = amount + 1 |
| Subsequence | Items kept in order, gaps allowed | "ACD" in "ABCD" |
| Substring | A contiguous piece, no gaps | "BC" in "ABCD" |
| Longest common subsequence (LCS) | The longest subsequence of both strings | "BCBA" |
| 2D table | vector<vector<int>> indexed by two positions |
dp[i][j] |
| Prefix | The first i characters of a string | a[0..i) |
| Reconstruction | Walking back through the table to read the actual answer | "BCBA" |
| Edit distance | Fewest inserts/deletes/replacements between strings | "chai" → "chair": 1 |
diff |
A tool that shows kept, removed and added lines, built on LCS | the mini project |
Summary
- DP = never solve the same subproblem twice. Write the recursion, add a memo (top-down), then turn it into a bottom-up table, often with O(1) extra space.
- Find the recurrence by asking what the last move / coin / character was.
- Climbing stairs:
ways(n) = ways(n-1) + ways(n-2): plain recursion made 3,672,623,805 calls forn = 45; the memo made 89. - Minimum coins: greedy biggest-first is wrong in general;
dp[a] = min(dp[a - c] + 1). Don't add 1 toINT_MAX: useamount + 1as infinity. - LCS:
dp[i][j]over prefixes; match → diagonal + 1, else the max of skipping one; the answer is in the corner, O(n × m).
Next episode: the interview round, the last episode of the series: an LRU cache (list + unordered_map), the top k frequent words (with a tie-break), and a mini inventory system with classes and the STL.