SyntaxPilot
Courses/C++ Coding Questions/Lesson 29
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

C++ Coding Questions · Lesson 29 of 30

Dynamic programming questions

climbing stairs (recursion vs memo vs table)minimum coins (coin change)longest common subsequence

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:

  1. Optimal substructure: the answer is built from answers to smaller versions of the same problem (a recurrence).
  2. 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

  1. What is dynamic programming? Solving a problem by combining answers to overlapping subproblems, each solved once and stored.
  2. What two properties make a problem a DP problem? Optimal substructure and overlapping subproblems.
  3. Memoization vs tabulation? Top-down recursion with a cache vs bottom-up loops over a table.
  4. Why is plain recursive Fibonacci slow? It recomputes the same values: about 1.618^n calls, exponential.
  5. 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.
  6. 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.
  7. Why not use INT_MAX as infinity? INT_MAX + 1 overflows (UB). Use a value bigger than any real answer but safe to add to, like amount + 1, or skip infinite entries.
  8. Time and space of coin change? O(amount × coins) and O(amount).
  9. Subsequence vs substring? A subsequence keeps order but allows gaps; a substring is contiguous.
  10. LCS recurrence? Match: dp[i-1][j-1] + 1; otherwise max(dp[i-1][j], dp[i][j-1]).
  11. How do you reconstruct the LCS itself? Walk back from dp[n][m], going diagonally on matches.
  12. How do you reduce LCS memory? Each row needs only the previous row: two rows, O(min(n, m)) space (for the length only).
  13. 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 for n = 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 to INT_MAX: use amount + 1 as 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.