SyntaxPilot
Courses/C++/Lesson 38
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++ · Lesson 38 of 40

DSA 3: dynamic programming

queued

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:

  1. Before working anything out, check the memo. If the answer is there, return it.
  2. 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
  • -1 means "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 separate vector<bool> done.)
  • memo is 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 that INF + 1 still loses every min, but small enough that INF + 1 doesn't overflow an int.
  • 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

  1. The stairs, with 1, 2 or 3 stairs at a time, for n = 30.
  2. Fewest coins for 11 with coins 1, 5 and 7. What does greedy say?
  3. Can exactly 7 cups be made from packets of 3 and 5? Which amounts up to 12 can?
  4. 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

  1. What is dynamic programming? Solving a problem by combining answers to smaller subproblems, computing each subproblem once and storing it.
  2. 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).
  3. 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.
  4. 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.
  5. 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.
  6. 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).
  7. 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.
  8. 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).