DSA Dynamic Programming

Tabulation

Why does filling a table left-to-right beat a recursive call tree here? At n = 10⁵, the recurrence is linear, but the stack is not a complexity guarantee.

Tabulation is DP: set , then fill in . Loop direction is part of the problem definition (0/1 vs unbounded knapsack).

Algorithm journey

Allocate the table

Size matches the state space (or a frontier).

Foundations every cell depends on.

Topological order of the state DAG.

Extract the answer cell

Optionally compress space or recover a witness.

What actually happens

Naive idea: recurse with memoization for every DP. Works until depth overflows, or until you need every cell and tight loops.

Better idea: treat states as a DAG. Fill , then each cell via a in dependency order. Time is still states × transitions; control flow is iterative.

The improved design still fails with the wrong loop direction (0/1 vs unbounded), reading overwritten rolling-array cells, or treating unreachable sentinels as real optima.

Invariant

Immediately before computing a state, every predecessor named by its recurrence already holds the correct subproblem answer. The transition establishes correctness for this state.

How to choose tabulation

1. Clear dependency order? If you can draw arrows from cells to predecessors, bottom-up is natural.

2. Need space rolling or no stack? Prefer tabulation and optional .

3. Sparse reachability? Full tables waste work; memoization or push-from-reachable may win.

Quantitative check

Climbing stairs with tabulation: O(n) time, O(1) space with two variables. Edit distance on two length-10³ strings: about 10⁶ cells. Same recurrence memoized still risks deep recursion on adversarial shapes.

Fibonacci Tabulation (Bottom-Up)

Iteratively building the solution array from left to right.

Step 0 of -1

Current (Being Filled)

Dependencies (Used)

Filled

How tabulation works

Create a Table (Array/Matrix)

Initialize a table (1D array, 2D matrix, etc.) to store solutions to all subproblems. Size depends on the problem's state space.

Fill Base Cases

Set the simplest subproblems (base cases) directly. These are the "foundation" that all other solutions build upon.

Fill Table Iteratively

Use loops to fill the table in order, ensuring each cell uses only previously computed cells. Follow the dependency order (smaller to larger subproblems).

Extract Final Answer

The answer to the original problem is in a specific cell (usually the last one). Simply return that value!

Dependency order is a topological sort

Treat each state as a vertex and each recurrence dependency as a directed edge. A valid loop nest is any topological order of that state DAG. Before writing loops, draw arrows from one representative cell to every cell it reads.

Prefix DP

If i reads i−1, iterate i upward.

Suffix DP

If i reads i+1, iterate i downward.

Interval DP

If [l,r] reads shorter ranges, iterate by increasing length.

Loop invariant: immediately before computing a state, every predecessor named by its recurrence already equals the correct subproblem answer. The transition then establishes correctness for this state.

Pull, push, and the loop-direction trap

Pull formulation

For each destination state, gather all predecessors. It maps directly to a recurrence and makes “computed before read” easy to audit.

Push formulation

For each reachable state, relax its outgoing successors. It naturally skips impossible states, but initialization and duplicate contributions need care.

Knapsack litmus test: updating capacity downward prevents the current item from feeding itself, producing 0/1 knapsack. Updating upward permits reuse and produces unbounded knapsack. One loop direction changes the problem definition.

Space compression versus reconstruction

Goal	Safe technique	What can go wrong
Score only	Keep the dependency frontier: two rows, one row, or a fixed ring buffer	Wrong update direction reads values overwritten in the same iteration
Recover one witness	Store parent/action per state, or recompute choices from a retained table	A rolling array may preserve the optimum value but erase the path/items/alignment
Low memory + witness	Checkpoint/recompute, divide-and-conquer reconstruction, or compact action bits	Recomputation trades memory back for time and implementation complexity

Sentinels and numeric safety

• Distinguish unreachable from a legitimate zero, negative optimum, or empty solution.
• Never compute MAX_VALUE + cost; guard the predecessor before addition.
• Use Python integers or Java long, and checked arithmetic when totals can approach the limit.
• For counts, state whether exact integers, saturation, or modulo arithmetic is required.
• Initialize min problems to a bounded infinity and max problems to negative infinity, not the same sentinel.
• Test impossible states, empty input, one state, ties, zero/negative values, and maximum bounds.

🔍 Did You Know? Tabulation vs Memoization

Both solve the same DP problems, but with opposite approaches:
• Memoization (Top-Down): Start with big problem, recursively break down, cache results
• Tabulation (Bottom-Up): Start with smallest problems, iteratively build up, fill table

Tabulation often has lower call overhead and uses less auxiliary stack space, but memoization is more intuitive and only solves needed subproblems!

💻 Classic Example: Fibonacci with Tabulation

✅ Tabulation Approach

Python

python

def fib_tabulation(n):
    """
    Bottom-up DP with tabulation
    Time: O(n) - single loop
    Space: O(n) - dp array
    
    Build solution from smallest (fib(0), fib(1)) to largest (fib(n))
    No recursion - just iteration!
    """
    if n < 0:
        raise ValueError("n must be non-negative")

    # Step 1: Create table
    if n <= 1:
        return n
    
    dp = [0] * (n + 1)
    
    # Step 2: Fill base cases
    dp[0] = 0
    dp[1] = 1
    
    # Step 3: Fill table iteratively (bottom-up)
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]  # Use previously computed values
    
    # Step 4: Return final answer
    return dp[n]

# Fast and no recursion!
print(fib_tabulation(100))
# Output: 354224848179261915075

# Let's see the table for fib(10)
def fib_tabulation_verbose(n):
    if n < 0:
        raise ValueError("n must be non-negative")
    dp = [0] * (n + 1)
    dp[0] = 0
    if n >= 1:
        dp[1] = 1
    
    print("Building table:")
    print(f"dp[0] = {dp[0]}")
    if n >= 1:
        print(f"dp[1] = {dp[1]}")
    
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
        print(f"dp[{i}] = dp[{i-1}] + dp[{i-2}] = {dp[i-1]} + {dp[i-2]} = {dp[i]}")
    
    return dp[n]

fib_tabulation_verbose(10)
# Building table:
# dp[0] = 0
# dp[1] = 1
# dp[2] = dp[1] + dp[0] = 1 + 0 = 1
# dp[3] = dp[2] + dp[1] = 1 + 1 = 2
# dp[4] = dp[3] + dp[2] = 2 + 1 = 3
# ...
# dp[10] = 55

Java

java

import java.math.BigInteger;

public class FibTabulation {
    /**
     * Bottom-up DP with tabulation
     * Time: O(n) - single loop
     * Space: O(n) - dp array
     * 
     * Build solution from smallest (fib(0), fib(1)) to largest (fib(n))
     * No recursion - just iteration!
     */
    public static BigInteger fibTabulation(int n) {
        if (n < 0) throw new IllegalArgumentException("n must be non-negative");
        // Step 1: Create table
        if (n <= 1) {
            return BigInteger.valueOf(n);
        }
        
        BigInteger[] dp = new BigInteger[n + 1];
        
        // Step 2: Fill base cases
        dp[0] = BigInteger.ZERO;
        dp[1] = BigInteger.ONE;
        
        // Step 3: Fill table iteratively (bottom-up)
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1].add(dp[i - 2]);
        }
        
        // Step 4: Return final answer
        return dp[n];
    }
    
    public static void main(String[] args) {
        // Fast and no recursion!
        BigInteger expected = new BigInteger("354224848179261915075");
        if (!fibTabulation(100).equals(expected)) throw new AssertionError();
        
        // Verbose version showing table building
        fibTabulationVerbose(10);
    }
    
    public static BigInteger fibTabulationVerbose(int n) {
        if (n < 0) throw new IllegalArgumentException("n must be non-negative");
        BigInteger[] dp = new BigInteger[n + 1];
        dp[0] = BigInteger.ZERO;
        if (n >= 1) dp[1] = BigInteger.ONE;
        
        System.out.println("Building table:");
        System.out.println("dp[0] = " + dp[0]);
        if (n >= 1) System.out.println("dp[1] = " + dp[1]);
        
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1].add(dp[i - 2]);
            System.out.println("dp[" + i + "] = dp[" + (i-1) + "] + dp[" + (i-2) + 
                             "] = " + dp[i-1] + " + " + dp[i-2] + " = " + dp[i]);
        }
        
        return dp[n];
        // Output: dp[10] = 55
    }
}

🚀 Space-Optimized Tabulation

Python

python

def fib_optimized(n):
    """
    Space-optimized tabulation
    Time: O(n)
    Space: O(1) - only two variables!
    
    Key insight: We only need last two values, not entire array
    This is a common tabulation optimization
    """
    if n < 0:
        raise ValueError("n must be non-negative")
    if n <= 1:
        return n
    
    # Only track last two values
    prev2 = 0  # fib(i-2)
    prev1 = 1  # fib(i-1)
    
    for i in range(2, n + 1):
        current = prev1 + prev2
        # Shift values for next iteration
        prev2 = prev1
        prev1 = current
    
    return prev1

print(fib_optimized(100))
# Output: 354224848179261915075
# Same result, but O(1) space instead of O(n)!

Java

java

import java.math.BigInteger;

public class FibOptimized {
    /**
     * Space-optimized tabulation
     * Time: O(n)
     * Space: O(1) - only two variables!
     * 
     * Key insight: We only need last two values, not entire array
     * This is a common tabulation optimization
     */
    public static BigInteger fibOptimized(int n) {
        if (n < 0) throw new IllegalArgumentException("n must be non-negative");
        if (n <= 1) {
            return BigInteger.valueOf(n);
        }
        
        // Only track last two values
        BigInteger prev2 = BigInteger.ZERO;  // fib(i-2)
        BigInteger prev1 = BigInteger.ONE;   // fib(i-1)
        
        for (int i = 2; i <= n; i++) {
            BigInteger current = prev1.add(prev2);
            // Shift values for next iteration
            prev2 = prev1;
            prev1 = current;
        }
        
        return prev1;
    }
    
    public static void main(String[] args) {
        BigInteger expected = new BigInteger("354224848179261915075");
        if (!fibOptimized(100).equals(expected)) throw new AssertionError();
        // Same result, but O(1) space instead of O(n)!
    }
}

Space Optimization: Tabulation often allows reducing space from O(n) or O(n²) to O(1) or O(n) by keeping only the values you actually need. This is harder with memoization!

🎯 Key Insight: Order Matters!

In tabulation, filling order is crucial. You must fill cells in an order where each cell only depends on previously filled cells:

✅ Good: for i in range(n): dp[i] = dp[i-1] + ...

❌ Bad: for i in range(n): dp[i] = dp[i+1] + ... (uses future value!)

For 2D tables, you might fill row-by-row, column-by-column, or diagonally - depends on dependencies!

🎯 More Tabulation Examples

Climbing Stairs (1D Tabulation)

Python

python

def climb_stairs(n):
    """
    Ways to climb n stairs (1 or 2 steps at a time)
    
    Time: O(n)
    Space: O(n) - can optimize to O(1)
    """
    if n < 0:
        raise ValueError("n must be non-negative")
    if n <= 1:
        return 1  # one empty sequence for n = 0
    if n == 2:
        return 2
    
    # dp[i] = ways to reach step i
    dp = [0] * (n + 1)
    dp[0] = 1
    dp[1] = 1  # 1 way to reach step 1
    dp[2] = 2  # 2 ways to reach step 2 (1+1 or 2)
    
    # Each step can be reached from step i-1 or i-2
    for i in range(3, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    
    return dp[n]

print(climb_stairs(5))  # 8 ways
print(climb_stairs(10))  # 89 ways

Java

java

import java.math.BigInteger;

public class ClimbingStairs {
    /**
     * Ways to climb n stairs (1 or 2 steps at a time)
     * 
     * Time: O(n)
     * Space: O(n) - can optimize to O(1)
     */
    public static BigInteger climbStairs(int n) {
        if (n < 0) throw new IllegalArgumentException("n must be non-negative");
        if (n <= 1) return BigInteger.ONE;
        if (n == 2) return BigInteger.TWO;
        
        // dp[i] = ways to reach step i
        BigInteger[] dp = new BigInteger[n + 1];
        dp[0] = BigInteger.ONE;
        dp[1] = BigInteger.ONE;  // 1 way to reach step 1
        dp[2] = BigInteger.TWO;  // 2 ways to reach step 2 (1+1 or 2)
        
        // Each step can be reached from step i-1 or i-2
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1].add(dp[i - 2]);
        }
        
        return dp[n];
    }
    
    public static void main(String[] args) {
        if (!climbStairs(5).equals(BigInteger.valueOf(8))) throw new AssertionError();
        if (!climbStairs(10).equals(BigInteger.valueOf(89))) throw new AssertionError();
    }
}

Longest Common Subsequence (2D Tabulation)

Python

python

def lcs_tabulation(s1, s2):
    """
    Longest Common Subsequence - 2D tabulation
    
    Time: O(m*n)
    Space: O(m*n) - can optimize to O(min(m,n))
    """
    m, n = len(s1), len(s2)
    
    # Create 2D table
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    # Fill table bottom-up
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i-1] == s2[j-1]:
                # Characters match - extend LCS
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                # Take max of skipping either character
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    
    return dp[m][n]

print(lcs_tabulation("ABCDGH", "AEDFHR"))  # 3 (ADH)
print(lcs_tabulation("AGGTAB", "GXTXAYB"))  # 4 (GTAB)
assert lcs_tabulation("🙂A", "🙂B") == 1

# Visualize the table for "ABC" and "AC"
def lcs_visualize(s1, s2):
    m, n = len(s1), len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i-1] == s2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    
    # Print table
    print("    ", "  ".join(s2))
    for i in range(m + 1):
        if i == 0:
            print("  ", dp[i])
        else:
            print(s1[i-1], " ", dp[i])
    
    return dp[m][n]

lcs_visualize("ABC", "AC")
#       A  C
#   [0, 0, 0]
# A  [0, 1, 1]
# B  [0, 1, 1]
# C  [0, 1, 2]

Java

java

public class LongestCommonSubsequence {
    /**
     * Longest Common Subsequence - 2D tabulation
     * 
     * Time: O(m*n)
     * Space: O(m*n) - can optimize to O(min(m,n))
     */
    public static int lcsTabulation(String s1, String s2) {
        int[] first = s1.codePoints().toArray();
        int[] second = s2.codePoints().toArray();
        int m = first.length;
        int n = second.length;
        
        // Create 2D table
        int[][] dp = new int[m + 1][n + 1];
        
        // Fill table bottom-up
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (first[i - 1] == second[j - 1]) {
                    // Characters match - extend LCS
                    dp[i][j] = dp[i-1][j-1] + 1;
                } else {
                    // Take max of skipping either character
                    dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
                }
            }
        }
        
        return dp[m][n];
    }
    
    public static void lcsVisualize(String s1, String s2) {
        int[] first = s1.codePoints().toArray();
        int[] second = s2.codePoints().toArray();
        int m = first.length;
        int n = second.length;
        int[][] dp = new int[m + 1][n + 1];
        
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (first[i - 1] == second[j - 1]) {
                    dp[i][j] = dp[i-1][j-1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
                }
            }
        }
        
        // Print table
        System.out.print("    ");
        for (int codePoint : second) {
            System.out.print(new String(Character.toChars(codePoint)) + "  ");
        }
        System.out.println();
        
        for (int i = 0; i <= m; i++) {
            if (i == 0) {
                System.out.print("  ");
            } else {
                System.out.print(new String(Character.toChars(first[i - 1])) + " ");
            }
            System.out.print(" [");
            for (int j = 0; j <= n; j++) {
                System.out.print(dp[i][j]);
                if (j < n) System.out.print(", ");
            }
            System.out.println("]");
        }
    }
    
    public static void main(String[] args) {
        System.out.println(lcsTabulation("ABCDGH", "AEDFHR"));  // 3 (ADH)
        System.out.println(lcsTabulation("AGGTAB", "GXTXAYB"));  // 4 (GTAB)
        if (lcsTabulation("🙂A", "🙂B") != 1) throw new AssertionError();
        
        System.out.println("\nVisualization for ABC and AC:");
        lcsVisualize("ABC", "AC");
        //       A  C
        //   [0, 0, 0]
        // A  [0, 1, 1]
        // B  [0, 1, 1]
        // C  [0, 1, 2]
    }
}

0/1 Knapsack (2D Tabulation)

Python

python

def knapsack(weights, values, capacity):
    """
    0/1 Knapsack - classic DP problem
    
    Time: O(n * capacity)
    Space: O(n * capacity) - can optimize to O(capacity)
    """
    if len(weights) != len(values) or capacity < 0:
        raise ValueError("invalid lengths or capacity")
    if any(weight < 0 for weight in weights):
        raise ValueError("weights must be non-negative")
    n = len(weights)
    
    # dp[i][w] = max value using first i items with capacity w
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    
    # Fill table
    for i in range(1, n + 1):
        for w in range(capacity + 1):
            # Option 1: Don't take item i-1
            dp[i][w] = dp[i-1][w]
            
            # Option 2: Take item i-1 (if it fits)
            if weights[i-1] <= w:
                dp[i][w] = max(dp[i][w], 
                              dp[i-1][w - weights[i-1]] + values[i-1])
    
    return dp[n][capacity]

weights = [1, 3, 4, 5]
values = [1, 4, 5, 7]
capacity = 7

print(knapsack(weights, values, capacity))  # 9 (items 2 and 3)

Java

java

public class Knapsack {
    /**
     * 0/1 Knapsack - classic DP problem
     * 
     * Time: O(n * capacity)
     * Space: O(n * capacity) - can optimize to O(capacity)
     */
    public static long knapsack(int[] weights, long[] values, int capacity) {
        if (weights.length != values.length || capacity < 0) {
            throw new IllegalArgumentException("invalid lengths or capacity");
        }
        int n = weights.length;
        for (int weight : weights) {
            if (weight < 0) throw new IllegalArgumentException("negative weight");
        }
        
        // dp[i][w] = max value using first i items with capacity w
        long[][] dp = new long[n + 1][capacity + 1];
        
        // Fill table
        for (int i = 1; i <= n; i++) {
            for (int w = 0; w <= capacity; w++) {
                // Option 1: Don't take item i-1
                dp[i][w] = dp[i-1][w];
                
                // Option 2: Take item i-1 (if it fits)
                if (weights[i-1] <= w) {
                    long take = Math.addExact(dp[i - 1][w - weights[i - 1]], values[i - 1]);
                    dp[i][w] = Math.max(dp[i][w], take);
                }
            }
        }
        
        return dp[n][capacity];
    }
    
    public static void main(String[] args) {
        int[] weights = {1, 3, 4, 5};
        long[] values = {1, 4, 5, 7};
        int capacity = 7;
        
        if (knapsack(weights, values, capacity) != 9L) throw new AssertionError();
    }
}

💡 Pro Tip: When to Use Tabulation

Choose tabulation over memoization when:

• Need all subproblems: You'll solve all subproblems anyway (no benefit to lazy evaluation)
• Avoid recursion: Deep recursion might cause stack overflow
• Space optimization: You can reduce space by keeping only needed values
• Performance critical: Eliminate recursion overhead for maximum speed
• Regular state space: States fit nicely in array/matrix structure

Avoid when: Recursive solution is much more natural, or only small subset of subproblems needed!

✅ Pros & ❌ Cons

✅ Advantages

✓No recursion overhead and often better memory locality
✓No stack overflow risk (iterative)
✓Easier to optimize space (rolling arrays)
✓Predictable memory usage
✓Better cache locality (sequential access)

❌ Disadvantages

✗Less intuitive than recursive thinking
✗Must determine correct filling order
✗Solves all subproblems (even if not needed)
✗Harder to implement for complex state spaces
✗Requires upfront table size calculation

💼 Real World Applications

📊 Spreadsheet Formulas

Excel/Google Sheets use tabulation when calculating formulas. Cells are computed in dependency order (bottom-up), ensuring each cell uses only previously calculated values.

Example: Excel formula recalculation

🧬 Sequence Alignment

Bioinformatics tools use tabulation for DNA/protein sequence alignment (Needleman-Wunsch algorithm). The 2D table shows alignment scores for all subsequence pairs.

Example: BLAST, genome sequencing

🎯 Resource Allocation

Operations research uses tabulation for knapsack-type problems: budget allocation, project selection, inventory management - all solved with bottom-up DP tables.

Example: Portfolio optimization, scheduling

📝 Text Processing

Edit distance (spell check), diff algorithms (git diff), and text similarity all use tabulation to build 2D tables comparing strings character-by-character.

Example: Autocorrect, version control

Exercises

0/1 knapsack with a 1D array: show why iterating capacity upward incorrectly allows item reuse. What invariant breaks?
Interval DP on length n = 200 with O(n³) splits: estimate operations. When would you seek Knuth optimization or another structure?
You need the optimum value and the chosen items, but only keep a rolling row. What extra information must you store or recompute?

Primary sources

Cormen et al., CLRS: bottom-up dynamic programming and table reconstruction.
Kleinberg & Tardos: iterative DP formulations (weighted interval scheduling, knapsack).
Competitive programming notes on loop order for 0/1 vs unbounded knapsack (AtCoder DP contest style editorials).

Takeaway

Tabulation is the same recurrence as memoization, executed in dependency order. Loop direction and bases are part of the proof.