Bytebook Compiler

Dynamic Programming

Dynamic Programming

Solve each subproblem once: overlapping subproblems and optimal substructure, memoisation vs tabulation, and DP solutions for Fibonacci and coin change.

5 min read4 runnable examples4-question quiz

Dynamic programming (DP) solves problems by combining solutions to subproblems — like divide and conquer — but for problems whose subproblems overlap. Instead of recomputing a subproblem every time it appears, DP solves it once and stores the answer.

A problem suits DP when it has:

  1. Optimal substructure — an optimal solution is built from optimal solutions to subproblems.
  2. Overlapping subproblems — the same subproblems recur many times.

The problem with plain recursion

C++
#include <iostream>
using namespace std;

long calls = 0;
long fib(int n) { calls++; return n < 2 ? n : fib(n - 1) + fib(n - 2); }

int main() {
    for (int n : {10, 20, 30}) {
        calls = 0;
        long f = fib(n);
        cout << "fib(" << n << ") = " << f << " took " << calls << " calls" << endl;
    }
    return 0;
}
Output
fib(10) = 55 took 177 calls
fib(20) = 6765 took 21891 calls
fib(30) = 832040 took 2692537 calls
Try it Yourself

fib(30) makes over a million calls to compute only 31 distinct values. That is exponential waste.

Approach 1: memoisation (top-down)

Keep the recursion, but cache each result the first time it is computed:

C++
#include <iostream>
#include <vector>
using namespace std;

vector<long long> memo(91, -1);
long long fib(int n) {
    if (n < 2) return n;
    if (memo[n] != -1) return memo[n];         // already solved
    return memo[n] = fib(n - 1) + fib(n - 2);
}

int main() {
    cout << "fib(90) = " << fib(90) << endl;   // instant: 91 subproblems, each solved once
    return 0;
}
Output
fib(90) = 2880067194370816120
Try it Yourself

Approach 2: tabulation (bottom-up)

Fill a table from the smallest subproblems upward, so every value you need is already there:

C++
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n = 90;
    vector<long long> dp(n + 1);
    dp[0] = 0; dp[1] = 1;
    for (int i = 2; i <= n; i++) dp[i] = dp[i - 1] + dp[i - 2];
    cout << "fib(90) = " << dp[n] << endl;

    long long a = 0, b = 1;                     // only the last two values are needed: O(1) space
    for (int i = 0; i < n; i++) { long long t = a + b; a = b; b = t; }
    cout << "fib(90) = " << a << " (constant space)" << endl;
    return 0;
}
Output
fib(90) = 2880067194370816120
fib(90) = 2880067194370816120 (constant space)
Try it Yourself
Memoisation (top-down) Tabulation (bottom-up)
Style recursive + cache iterative table
Solves only the subproblems actually needed every subproblem
Overhead function calls, recursion depth none
Easier to write often yes — follows the recurrence needs a correct fill order
Space saving tricks harder easy (keep only needed rows)

The DP recipe

  1. Define the state: what does dp[i] (or dp[i][j]) mean, in words?
  2. Write the recurrence: how does a state depend on smaller states?
  3. Base cases.
  4. Fill order: make sure dependencies are computed first.
  5. Answer: which cell holds the final result? (Optionally trace back the choices.)

Example: coin change

Coins {1, 3, 4}, amount 6. Greedy gave 3 coins; DP finds the true minimum.

State: dp[x] = minimum number of coins that make amount x. Recurrence: dp[x] = 1 + min(dp[x − c]) over coins c ≤ x. Base: dp[0] = 0.

C++
#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int main() {
    vector<int> coins = {1, 3, 4};
    int amount = 6;
    vector<int> dp(amount + 1, INT_MAX), choice(amount + 1, -1), ways(amount + 1, 0);
    dp[0] = 0;
    for (int x = 1; x <= amount; x++)
        for (int c : coins)
            if (c <= x && dp[x - c] != INT_MAX && dp[x - c] + 1 < dp[x]) { dp[x] = dp[x - c] + 1; choice[x] = c; }

    cout << "x:     "; for (int x = 0; x <= amount; x++) cout << x << " ";
    cout << "\ndp[x]: "; for (int x = 0; x <= amount; x++) cout << dp[x] << " ";
    cout << "\nminimum coins for " << amount << " = " << dp[amount] << ": ";
    for (int x = amount; x > 0; x -= choice[x]) cout << choice[x] << " ";
    cout << endl;

    ways[0] = 1;                                   // number of ways (order does not matter)
    for (int c : coins) for (int x = c; x <= amount; x++) ways[x] += ways[x - c];
    cout << "number of ways to make " << amount << " = " << ways[amount] << endl;
    return 0;
}
Output
x:     0 1 2 3 4 5 6 
dp[x]: 0 1 2 1 1 2 2 
minimum coins for 6 = 2: 3 3 
number of ways to make 6 = 4
Try it Yourself

Time O(amount × coins). The second loop answers a different question — how many combinations — with the coin loop outside so each combination is counted once.

Test yourself

4 questions · pick an answer to check it instantly

  1. 1

    Which property distinguishes DP from divide and conquer?

  2. 2

    What is memoisation?

  3. 3

    For coins {1, 3, 4}, what is dp[6] (minimum coins for 6)?

  4. 4

    What is the time complexity of tabulated Fibonacci?

Esc
↑↓ move↵ open