Introduction to Dynamic Programming

Dynamic programming (DP) means don’t recalculate work you’ve already done. Many DP problems start as natural recursions; the usual path is: write the recursion, then cache repeated states. That is top-down DP with memoization (“memo” like a notepad — not “memorization”).

This lesson follows CP-Algorithms — Introduction to Dynamic Programming.

Fibonacci as the running example

f(n) = f(n−1) + f(n−2)   for n ≥ 2
f(0) = 0,  f(1) = 1

int f(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    return f(n - 1) + f(n - 2);
}

Naive recursion is about O(2ⁿ): each call fans into two similar calls. f(29) alone can exceed a million calls.

Top-down: memoization

There are only O(n) distinct subproblems: f(n)…f(0). Solve each once, store the answer, reuse later → O(n) time.

const int MAXN = 100;
bool found[MAXN];
int memo[MAXN];

int f(int n) {
    if (found[n]) return memo[n];
    if (n == 0) return 0;
    if (n == 1) return 1;

    found[n] = true;
    return memo[n] = f(n - 1) + f(n - 2);
}

f(29) drops from ~1e6 calls to tens of calls. After that you often hit integer overflow before time limits (f(46) is the last Fibonacci that fits in signed 32-bit).

Other memo containers

Arrays are best when indices are dense (O(1)). Generically:

unordered_map<int, int> memo; // average O(1)
// or
map<int, int> memo;         // O(log n) per lookup → O(n log n) total

Maps/hash maps shine when the state is a string, vector, or sparse key — not for plain Fibonacci.

Layman’s runtime:

(work per subproblem) × (number of subproblems)

Top-down starts at the query and recurses toward base cases, caching on the way.

Bottom-up: tabulation

Flip the order: initialize bases, then extend upward with the same recurrence.

const int MAXN = 100;
int fib[MAXN];

int f(int n) {
    fib[0] = 0;
    fib[1] = 1;
    for (int i = 2; i <= n; i++)
        fib[i] = fib[i - 1] + fib[i - 2];
    return fib[n];
}

Only the last two values matter, so memory can drop from O(n) to O(1):

const int MAX_SAVE = 3;
int fib[MAX_SAVE];

int f(int n) {
    fib[0] = 0;
    fib[1] = 1;
    for (int i = 2; i <= n; i++)
        fib[i % MAX_SAVE] =
            fib[(i - 1) % MAX_SAVE] + fib[(i - 2) % MAX_SAVE];
    return fib[n % MAX_SAVE];
}

That’s DP in one line: don’t repeat work.

🧪 Memo vs naive call counts for f(20)

Interactive walkthrough

Classic DP problems (study list)

Name	Idea
0-1 Knapsack	Max value with weight ≤ W
Subset Sum	Exists subset summing to T?
LIS	Longest strictly increasing subsequence
Grid paths	Count paths (1,1)→(N,M) with right/down moves
LCS	Longest common subsequence of two strings
Longest path in DAG	DP on topo order
LPS	Longest palindromic subsequence
Rod cutting	Min cost of ordered cuts
Edit distance	Min insert/delete/replace

Related flavors: bitmask DP, digit DP, DP on trees. Related on this site: Divide and Conquer DP, Convex Hull Trick.

Check: memoization

Quiz

Top-down DP

1 / 4

Memoization means…

Pick an answer to see if you are right.

Check: bottom-up

Quiz

Bottom-up DP

1 / 4

Bottom-up Fibonacci starts from…

Pick an answer to see if you are right.

Practice drills

Activity: Naive fib

n (0 ≤ n ≤ 20). Print f(n) with the plain recursive definition (no memo required for this drill).

Contest problems

From CP-Algorithms:

• LeetCode 1137 — N-th Tribonacci Number
• LeetCode 118 — Pascal's Triangle
• LeetCode 1025 — Divisor Game
• Codeforces — Vacations

Cheat sheet

Idea	Takeaway
Goal	Avoid recomputing overlapping subproblems
Top-down	Recursion + memo array/map
Bottom-up	Fill table from bases
Runtime	(#states) × (transition work)
Memory	Often reducible with rolling arrays
Next	Classic knapsack / LIS / LCS / paths