Lesson 1 · Problem-solving methods

Dynamic Programming

Dynamic Programming (DP) is an optimization technique that solves complex problems by breaking them down into simpler, overlapping subproblems. It stores the results of these subproblems so that each is only solved once.

Overlapping subproblems

If a recursive algorithm repeatedly solves the exact same problem with the exact same inputs, it has overlapping subproblems. For example, in the naive recursive Fibonacci algorithm, fib(3) is calculated multiple times.

DP solves this by caching the result of fib(3) the first time it is computed and reusing it for all subsequent calls.

Prevents exponential time explosions
Requires a cache (array or hash map)
Classic examples: Fibonacci, climbing stairs

Optimal substructure

A problem has optimal substructure if its overall optimal solution can be constructed from the optimal solutions of its subproblems. If you want the shortest path from A to C through B, it must be the shortest path from A to B plus the shortest path from B to C.

If the subproblems are not independent (e.g., finding the longest simple path in a graph), DP cannot be safely applied.

Subproblems must be independent
Used in shortest paths, knapsack
Formulate a state transition equation

Key reference

Terms, operations, and practical uses

Core vocabulary

StateA set of parameters that uniquely identify a specific subproblem (e.g., index and current_capacity).
TransitionThe mathematical relationship between a state and its smaller sub-states (the recurrence relation).
MemoizationCaching the results of expensive function calls to return the cached result when the same inputs occur again (Top-Down).

Key concepts

Overlapping SubproblemsWhen a problem is broken down into subproblems which are reused several times.
Optimal SubstructureWhen an optimal solution can be constructed efficiently from optimal solutions of its subproblems.
TabulationSolving a DP problem by filling up a table (array) iteratively from the smallest subproblem up to the final answer (Bottom-Up).

Common patterns

1D DPProblems where the state can be represented by a single integer, like climbing stairs.
2D DPProblems where the state requires two integers, such as navigating a grid or comparing two strings.
KnapsackA classic pattern involving choosing items with weights and values to maximize total value within a capacity.

Code example

Calculate Fibonacci sequence using Bottom-Up DP

def fib(n):
    if n <= 1: return n
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]
print(fib(5))

int fib(int n) {
    if (n <= 1) return n;
    vector<int> dp(n + 1, 0);
    dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2];
    }
    return dp[n];
}

static int fib(int n) {
    if (n <= 1) return n;
    int[] dp = new int[n + 1];
    dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2];
    }
    return dp[n];
}

Inputn = 5

Output5

Example

Run the example step by step

Output

Top-Down (Memoization)

Top-down DP starts at the final goal and recursively breaks it down. Before making a recursive call, it checks if the answer is already in the cache (memo).

This approach is intuitive as it naturally follows the recursive formula. It only computes the states that are strictly necessary to reach the answer.

Uses recursion + cache
Easier to write from a recursive formula
May cause stack overflow on deep inputs

Bottom-Up (Tabulation)

Bottom-up DP starts at the smallest base cases and iteratively computes larger subproblems until the final goal is reached. It usually involves nested loops filling a table (array).

Since it is iterative, there is no recursion overhead. Furthermore, it often allows for space optimization by only keeping the last few computed values instead of the entire table.

Uses iteration + table
No recursion limit issues
Often enables O(1) space optimization