Dynamic Programming — Complete Step-by-Step Guide

Module 14 — Dynamic Programming: Solving big problems by remembering smaller ones Structured as Topic → Plain-English Explanation → Real Code → Visual Diagram → Complexity → Common Pitfalls.

1. Core Principles: Overlapping Subproblems & Optimal Substructure

Dynamic programming (DP) is an optimization method applicable to problems that exhibit two defining mathematical characteristics:

1. Optimal Substructure: The optimal solution to the overall problem contains within it the optimal solutions to its subproblems. If you know the best path from $A$ to $B$ and from $B$ to $C$, the best path from $A$ to $C$ is simply their combination.
2. Overlapping Subproblems: The same subproblems are solved repeatedly across different branches of the recursive decision tree.

The 5-Step DP Mental Framework

1. Define the State: What parameters uniquely describe a subproblem? (e.g., dp[i][w] = maximum value using a subset of first $i$ items with capacity $w$).
2. Identify the Base Cases: What are the smallest, trivial subproblems with known answers? (e.g., capacity 0 yields value 0).
3. Formulate the Recurrence Relation (State Transition): How does the current state depend on previously computed states?
4. Determine the Computation Order: In what order must the table be filled so that dependencies are always computed before they are needed?
5. Space Optimization: Can we reduce memory from $O(n^2)$ to $O(n)$ by keeping only the previous row or rolling variables?

2. Memoization (Top-Down) vs Tabulation (Bottom-Up)

• Top-Down (Memoization): You maintain the natural, intuitive recursive tree structure from the main problem down to base cases, but wrap it with a cache (hash map or array). If the state was previously solved, return the cached result in $O(1)$ time.
• Bottom-Up (Tabulation): You start by explicitly filling the base cases in an iterative array or matrix, systematically building up solutions to larger subproblems until the target state is reached. This completely eliminates function call stack overhead.

// 1. Memoization (Top-Down with cache)
unordered_map<int, long long> memo;
long long fibMemo(int n) {
    if (n <= 1) return n;
    if (memo.count(n)) return memo[n];
    return memo[n] = fibMemo(n - 1) + fibMemo(n - 2);
}

// 2. Tabulation (Bottom-Up iterative table)
long long fibTab(int n) {
    if (n <= 1) return n;
    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];
    }
    return dp[n];
}

// 3. Space-Optimized Tabulation (O(1) Memory)
long long fibOptimized(int n) {
    if (n <= 1) return n;
    long long prev2 = 0, prev1 = 1;
    for (int i = 2; i <= n; i++) {
        long long curr = prev1 + prev2;
        prev2 = prev1;
        prev1 = curr;
    }
    return prev1;
}

3. The 0/1 Knapsack Problem Walkthrough

Given $n$ items, each with a weight $wt[i]$ and value $val[i]$, and a knapsack of max capacity $W$, determine the maximum value achievable without exceeding $W$. Each item can either be taken once ($1$) or left behind ($0$).

Recurrence Relation

For item $i$ and remaining capacity $w$:

• If $wt[i-1] > w$: We cannot take item $i implies dp[i][w] = dp[i-1][w]$.
• If $wt[i-1] le w$: We take the maximum of excluding or including the item: $$ ext{dp}[i][w] = maxBig( ext{dp}[i-1][w], ; val[i-1] + ext{dp}[i-1][w - wt[i-1]]Big)$$

int knapsack01(int W, const vector<int>& wt, const vector<int>& val) {
    int n = wt.size();
    vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));

    for (int i = 1; i <= n; i++) {
        for (int w = 0; w <= W; w++) {
            if (wt[i - 1] <= w) {
                dp[i][w] = max(dp[i - 1][w], val[i - 1] + dp[i - 1][w - wt[i - 1]]);
            } else {
                dp[i][w] = dp[i - 1][w];
            }
        }
    }
    return dp[n][W];
}

4. Complexity & Pattern Summary