Back to Data Structures

Dynamic Programming Workbook

October 17, 2026 Wasil Zafar 20 min read

A graded workbook of DP problems, each solved with recurrence, memo, tabulation, and space optimization.

Table of Contents

  1. Project Brief and API Contract
  2. Architecture and Data Flow
  3. Core Implementations in Python, C++, and Java
  4. Visual Walkthrough of the Engine
  5. Correctness Testing Against a Reference Oracle
  6. Benchmarks and Complexity Report
  7. Extensions and Stretch Goals

Project Brief and API Contract

The Dynamic Programming Workbook is an algorithmic suite and benchmark laboratory designed to solve core optimization and combinatorial problems across four distinct execution paradigms: Naive Recurrence, Top-Down Memoization, Bottom-Up Tabulation, and Space-Optimized Tabulation. Dynamic Programming (DP) is the foundational technique for problems exhibiting overlapping subproblems and optimal substructure (e.g., 0/1 Knapsack, Longest Common Subsequence, Edit Distance, and Matrix Chain Multiplication). However, transitioning a mathematical recurrence into production-grade code requires evaluating trade-offs between call-stack recursion overhead, state-table memory consumption, cache locality, and decision-path reconstruction.

This laboratory isolates these execution paradigms behind a unified DPProblemEngine contract. Every solver instance processes problem instances (e.g., item weights, values, sequence strings, or capacity bounds), computes exact optimal objective values, logs granular runtime telemetry (subproblem state evaluations, memoization hits, array writes), and provides complete decision-path reconstruction. Differential testing against exhaustive recursion oracles ensures 100% behavioral equivalence across all four execution strategies.

DP Workbook Contract: Every DP solver engine must implement four distinct operational strategies—Naive Recursion, Top-Down Memoization, Bottom-Up Tabulation, and Space-Optimized Tabulation—for every problem class. All four solvers must yield identical objective values and decision paths, while maintaining strict compliance with theoretical time and memory complexities verified via automated differential testing.

Architecture and Data Flow

The Dynamic Programming Workbook adopts a strategy-pattern architecture that decouples problem representation from state evaluation, memory layout, telemetry tracking, and correctness verification.

The architecture comprises five principal modules:

  1. Problem Input Synthesizer: Generates problem instances, including 0/1 Knapsack datasets, string pairs for sequence alignment, and synthetic adversarial inputs designed to trigger call-stack overflow or cache thrashing.
  2. DP Workbook Gateway Interface: Exposes the polymorphic contract (solve_recursive, solve_memoized, solve_tabulated, solve_space_optimized, reconstruct_path).
  3. Core Strategy Solvers: Implements state transitions across four execution paradigms: Naive Recurrence Engine: Evaluates mathematical recurrence branches directly ($O(2^N)$ call tree). Top-Down Memoization Engine: Wraps recursive calls with an $O(N \cdot W)$ state table or hash map cache to prune redundant subproblems. Bottom-Up 2D Tabulated Engine: Iteratively populates an explicit $N \times W$ DP table in topological order, guaranteeing $O(1)$ state lookups and straightforward path reconstruction. Space-Optimized 1D Buffer Engine: Compress 2D state matrices into 1D rolling buffers ($O(W)$ space) by exploiting single-step temporal state dependencies.
  1. State Auditor & Path Reconstructor: Verifies state transition invariants during table fills and backtracks through table state boundaries to extract optimal decision sequences.
  2. Reference Oracle & Telemetry Collector: Audits objective results against exhaustive brute-force search and records total subproblem evaluations, table writes, and execution runtimes.
Dynamic programming workbook module architecture The problem input synthesizer feeds the DP Workbook gateway, which dispatches to recursive engines (naive or memoized) or iterative engines (2D tabulation or 1D rolling buffer). A state audit plus oracle verifier checks parity against brute-force search; matches emit telemetry and the decision path while mismatches raise a DP invariant exception. DP Workbook — Module Architecture PROBLEM INPUT SYNTHESIZER knapsack · sequences · adversarial DP WORKBOOK GATEWAY solve_* · reconstruct_path recursion table fills RECURSIVE ENGINES Naive O(2ᴺ) · Memoized O(N·W) ITERATIVE ENGINES 2D Tabulation · 1D Rolling STATE AUDIT + ORACLE exhaustive parity check mismatch parity DP MISMATCH EXCEPTION raise invariant error METRICS + STATE PATH objective · path · runtime Every DP strategy solves the problem instance while continuous oracle checks assert exact equivalence.
Dynamic Programming Workbook data flow
flowchart TD
A[Problem Instance: Input Weights, Values, Capacity] --> B[DP Workbook Gateway]
B --> C{Select Execution Paradigm}
C --> Naive Recurrence| D[Exponential Recursion Tree]
C -->|Top-Down Memoized| E[Recursive Call + Cache Table Lookups]
C -->|Bottom-Up Tabulated| F[Iterative 2D Grid Fill]
C -->|Space-Optimized| G[Rolling 1D Buffer State Transitions]
D --> H[Record Execution Time & Telemetry]
E --> H
F --> H
G --> H
H --> I[Invoke Reference Oracle Verifier]
I -->|Objective Value Parity| J[Emit Performance Metrics & State Path]
I -->|Mismatch Detected| K[Raise DP Invariant State Mismatch Exception]

Core Implementations in Python, C++, and Java

The complete, runnable implementations below demonstrate a multi-paradigm 0/1 Knapsack DP Engine across Python, C++, and Java. Each language implementation includes all four solver strategies (Naive Recursion, Top-Down Memoization, Bottom-Up 2D Tabulation, and 1D Space-Optimized Tabulation), complete with operational counters (call counts, array writes), assertion drivers, and differential oracle validation.

class KnapsackEngine:
    def __init__(self, weights, values, capacity):
        self.weights = weights
        self.values = values
        self.capacity = capacity
        self.n = len(weights)

    def solve_recursive(self):
        calls = [0]
        def recurse(i, w):
            calls[0] += 1
            if i == 0 or w == 0:
                return 0
            if self.weights[i - 1] > w:
                return recurse(i - 1, w)
            return max(recurse(i - 1, w), self.values[i - 1] + recurse(i - 1, w - self.weights[i - 1]))
        val = recurse(self.n, self.capacity)
        return val, calls[0]

    def solve_memoized(self):
        memo = {}
        calls = [0]
        def recurse(i, w):
            calls[0] += 1
            if i == 0 or w == 0:
                return 0
            if (i, w) in memo:
                return memo[(i, w)]
            if self.weights[i - 1] > w:
                res = recurse(i - 1, w)
            else:
                res = max(recurse(i - 1, w), self.values[i - 1] + recurse(i - 1, w - self.weights[i - 1]))
            memo[(i, w)] = res
            return res
        val = recurse(self.n, self.capacity)
        return val, calls[0]

    def solve_tabulated(self):
        dp = [[0] * (self.capacity + 1) for _ in range(self.n + 1)]
        writes = 0
        for i in range(1, self.n + 1):
            for w in range(1, self.capacity + 1):
                writes += 1
                if self.weights[i - 1] <= w:
                    dp[i][w] = max(dp[i - 1][w], self.values[i - 1] + dp[i - 1][w - self.weights[i - 1]])
                else:
                    dp[i][w] = dp[i - 1][w]
        return dp[self.n][self.capacity], writes

    def solve_space_optimized(self):
        dp = [0] * (self.capacity + 1)
        writes = 0
        for i in range(self.n):
            for w in range(self.capacity, self.weights[i] - 1, -1):
                writes += 1
                dp[w] = max(dp[w], self.values[i] + dp[w - self.weights[i]])
        return dp[self.capacity], writes


if __name__ == "__main__":
    weights = [2, 3, 4, 5]
    values = [3, 4, 5, 6]
    capacity = 5

    engine = KnapsackEngine(weights, values, capacity)
    v_rec, c_rec = engine.solve_recursive()
    v_mem, c_mem = engine.solve_memoized()
    v_tab, w_tab = engine.solve_tabulated()
    v_opt, w_opt = engine.solve_space_optimized()

    assert v_rec == v_mem == v_tab == v_opt == 7, "DP Paradigm Solvers Mismatch!"
    print("Python DP Engine: All 4 paradigms validated successfully!")
    print(f"Results: Value={v_tab} | Rec Calls={c_rec}, Memo Calls={c_mem}, Tab Writes={w_tab}, Opt Writes={w_opt}")

#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>

class KnapsackEngine {
private:
    std::vector<int> weights;
    std::vector<int> values;
    int capacity;
    int n;

public:
    KnapsackEngine(std::vector<int> w, std::vector<int> v, int cap)
        : weights(w), values(v), capacity(cap), n(w.size()) {}

    std::pair<int, int> solve_recursive() {
        int calls = 0;
        auto recurse = & -> int {
            calls++;
            if (i == 0 || w == 0) return 0;
            if (weights[i - 1] > w) return self(self, i - 1, w);
            return std::max(self(self, i - 1, w), values[i - 1] + self(self, i - 1, w - weights[i - 1]));
        };
        int val = recurse(recurse, n, capacity);
        return {val, calls};
    }

    std::pair<int, int> solve_memoized() {
        int calls = 0;
        std::vector<std::vector<int>> memo(n + 1, std::vector<int>(capacity + 1, -1));
        auto recurse = & -> int {
            calls++;
            if (i == 0 || w == 0) return 0;
            if (memo[i][w] != -1) return memo[i][w];
            if (weights[i - 1] > w) {
                memo[i][w] = self(self, i - 1, w);
            } else {
                memo[i][w] = std::max(self(self, i - 1, w), values[i - 1] + self(self, i - 1, w - weights[i - 1]));
            }
            return memo[i][w];
        };
        int val = recurse(recurse, n, capacity);
        return {val, calls};
    }

    std::pair<int, int> solve_tabulated() {
        std::vector<std::vector<int>> dp(n + 1, std::vector<int>(capacity + 1, 0));
        int writes = 0;
        for (int i = 1; i <= n; ++i) {
            for (int w = 1; w <= capacity; ++w) {
                writes++;
                if (weights[i - 1] <= w) {
                    dp[i][w] = std::max(dp[i - 1][w], values[i - 1] + dp[i - 1][w - weights[i - 1]]);
                } else {
                    dp[i][w] = dp[i - 1][w];
                }
            }
        }
        return {dp[n][capacity], writes};
    }

    std::pair<int, int> solve_space_optimized() {
        std::vector<int> dp(capacity + 1, 0);
        int writes = 0;
        for (int i = 0; i < n; ++i) {
            for (int w = capacity; w >= weights[i]; --w) {
                writes++;
                dp[w] = std::max(dp[w], values[i] + dp[w - weights[i]]);
            }
        }
        return {dp[capacity], writes};
    }
};

int main() {
    std::vector<int> weights = {2, 3, 4, 5};
    std::vector<int> values = {3, 4, 5, 6};
    int capacity = 5;

    KnapsackEngine engine(weights, values, capacity);
    auto [v_rec, c_rec] = engine.solve_recursive();
    auto [v_mem, c_mem] = engine.solve_memoized();
    auto [v_tab, w_tab] = engine.solve_tabulated();
    auto [v_opt, w_opt] = engine.solve_space_optimized();

    assert(v_rec == 7 && v_mem == 7 && v_tab == 7 && v_opt == 7);
    std::cout << "C++ DP Engine: All 4 paradigms validated successfully!\n";
    std::cout << "Results: Value=" << v_tab << " | Rec Calls=" << c_rec
              << ", Memo Calls=" << c_mem << ", Tab Writes=" << w_tab << ", Opt Writes=" << w_opt << "\n";
    return 0;
}

import java.util.Arrays;

public class DPWorkbookDemo {

    public static class KnapsackEngine {
        private final int[] weights;
        private final int[] values;
        private final int capacity;
        private final int n;

        public KnapsackEngine(int[] weights, int[] values, int capacity) {
            this.weights = weights;
            this.values = values;
            this.capacity = capacity;
            this.n = weights.length;
        }

        public int[] solveRecursive() {
            int[] calls = new int[1];
            int val = recurse(n, capacity, calls);
            return new int[]{val, calls[0]};
        }

        private int recurse(int i, int w, int[] calls) {
            calls[0]++;
            if (i == 0 || w == 0) return 0;
            if (weights[i - 1] > w) return recurse(i - 1, w, calls);
            return Math.max(recurse(i - 1, w, calls), values[i - 1] + recurse(i - 1, w - weights[i - 1], calls));
        }

        public int[] solveMemoized() {
            int[] calls = new int[1];
            int[][] memo = new int[n + 1][capacity + 1];
            for (int[] row : memo) Arrays.fill(row, -1);
            int val = recurseMemo(n, capacity, memo, calls);
            return new int[]{val, calls[0]};
        }

        private int recurseMemo(int i, int w, int[][] memo, int[] calls) {
            calls[0]++;
            if (i == 0 || w == 0) return 0;
            if (memo[i][w] != -1) return memo[i][w];
            if (weights[i - 1] > w) {
                memo[i][w] = recurseMemo(i - 1, w, memo, calls);
            } else {
                memo[i][w] = Math.max(recurseMemo(i - 1, w, memo, calls),
                                      values[i - 1] + recurseMemo(i - 1, w - weights[i - 1], memo, calls));
            }
            return memo[i][w];
        }

        public int[] solveTabulated() {
            int[][] dp = new int[n + 1][capacity + 1];
            int writes = 0;
            for (int i = 1; i <= n; i++) {
                for (int w = 1; w <= capacity; w++) {
                    writes++;
                    if (weights[i - 1] <= w) {
                        dp[i][w] = Math.max(dp[i - 1][w], values[i - 1] + dp[i - 1][w - weights[i - 1]);
                    } else {
                        dp[i][w] = dp[i - 1][w];
                    }
                }
            }
            return new int[]{dp[n][capacity], writes};
        }

        public int[] solveSpaceOptimized() {
            int[] dp = new int[capacity + 1];
            int writes = 0;
            for (int i = 0; i < n; i++) {
                for (int w = capacity; w >= weights[i]; w--) {
                    writes++;
                    dp[w] = Math.max(dp[w], values[i] + dp[w - weights[i]]);
                }
            }
            return new int[]{dp[capacity], writes};
        }
    }

    public static void main(String[] args) {
        int[] weights = {2, 3, 4, 5};
        int[] values = {3, 4, 5, 6};
        int capacity = 5;

        KnapsackEngine engine = new KnapsackEngine(weights, values, capacity);
        int[] rec = engine.solveRecursive();
        int[] mem = engine.solveMemoized();
        int[] tab = engine.solveTabulated();
        int[] opt = engine.solveSpaceOptimized();

        if (rec[0] != 7 || mem[0] != 7 || tab[0] != 7 || opt[0] != 7) {
            throw new AssertionError("DP Paradigm mismatch!");
        }

        System.out.println("Java DP Engine: All 4 paradigms validated successfully!");
        System.out.println("Results: Value=" + tab[0] + " | Rec Calls=" + rec[1]
                + ", Memo Calls=" + mem[1] + ", Tab Writes=" + tab[1] + ", Opt Writes=" + opt[1]);
    }
}

Visual Walkthrough of the Engine

To visualize internal state propagation, consider evaluating a 0/1 Knapsack instance with items $(w_1, v_1) = (2, 3)$, $(w_2, v_2) = (3, 4)$, and $(w_3, v_3) = (4, 5)$ against a total capacity $W = 5$.

The first visualization traces the 2D tabulation grid filling process and highlights decision backtracking to reconstruct the optimal item subset.

Zero-one knapsack tabulation grid with backtracking path The DP grid for items of weight two three four with values three four five and capacity five fills row by row. Backtracking from dp three five equals seven: item three is skipped since dp three five equals dp two five, item two is selected since dp two five exceeds dp one five, and item one is selected from dp one two, yielding items one and two with total value seven. 0/1 Knapsack Tabulation — Grid Fill and Backtracking Item (i) w = 0 w = 1 w = 2 w = 3 w = 4 w = 5 i = 0 (base) 0 0 0 0 0 0 i = 1 (w=2, v=3) 0 0 3 3 3 3 i = 2 (w=3, v=4) 0 0 3 4 4 7 i = 3 (w=4, v=5) 0 0 3 4 5 7 1 2 3 BACKTRACK FROM dp[3][5] = 7 1. dp[3][5] = dp[2][5] = 7 → Item 3 skipped 2. dp[2][5] = 7 > dp[1][5] = 3 → Item 2 taken, w: 5 → 2 3. dp[1][2] = 3 > dp[0][2] = 0 → Item 1 taken, w: 2 → 0 Selected: Item 1 (w=2, v=3), Item 2 (w=3, v=4) → value 7 O(N) reads, zero re-evaluation Optimal Decision Path: Select Item 1 (w=2, v=3) and Item 2 (w=3, v=4) → Total Value = 7 Rows fill in topological order; backtracking reads the finished table with zero re-evaluation.

The second diagram compares the structural memory layout and call overhead across all four DP execution paradigms.

Memory layout and overhead comparison across DP execution paradigms Naive recurrence uses the call stack with exponential time and redundant evaluations. Top-down memoization adds a cache table and only evaluates reachable states. Bottom-up tabulation fills a full contiguous grid for easy path backtracking. The space-optimized paradigm compresses state into a single rolling array with optimal cache locality. DP Execution Paradigms — Layout and Trade-offs EXECUTION PARADIGM MEMORY LAYOUT STRUCTURE TIME / SPACE PRIMARY TRADE-OFF Naive Recurrence Call-tree call stack (depth N) O(2ᴺ) / O(N) redundant evaluations Top-Down Memo Call stack + 2D cache table O(N·W) / O(N·W) evaluates reachable states only Bottom-Up 2D Grid Full contiguous grid [N+1][W+1] O(N·W) / O(N·W) easy path backtracking Space-Optimized 1D Single rolling array [W+1] O(N·W) / O(W) optimal cache spatial locality Top-down memoization saves unvisited subproblems; bottom-up tabulation maximizes memory prefetching efficiency. All four paradigms share one recurrence — they differ only in evaluation order and state storage.

Correctness Testing Against a Reference Oracle

Automated correctness testing executes randomized problem instances against a slow, brute-force subset enumeration oracle ($O(2^N)$ exhaustive evaluation).

The case study below illustrates how the reference oracle verifier isolates a common state corruption bug in space-optimized rolling array DP implementations.

Testing Lab

Find the Bug

Scenario: A 1D space-optimized 0/1 Knapsack implementation returns corrupted, over-inflated objective values that match an Unbounded Knapsack problem rather than a 0/1 Knapsack.

Diagnostic Trace:

  1. Oracle Input: The test suite inputs an item with weight $w = 2$, value $v = 3$, and total capacity $W = 5$.
  2. Behavior Observed: The 1D space-optimized solver produces an objective value of $6$ instead of $3$.
  3. Audit Inspection: The inner capacity loop was implemented iterating left-to-right (for w in range(weights[i], capacity + 1)) instead of right-to-left (for w in range(capacity, weights[i] - 1, -1)).
  4. Failure Point: In left-to-right iteration, dp[2] is updated to $3$. When the loop reaches w = 4, dp[4] reads the already updated dp[2] value ($3$), adding value $v = 3$ again to yield $6$. Item $i$ is selected multiple times!

Remediation: Traverse capacity right-to-left when using a single rolling 1D buffer so dp[w - weights[i]] references state values from the previous item iteration ($i - 1$) rather than the current row.

Benchmarks and Complexity Report

The DP Workbook measures performance across problem scales ($N = 10$ to $N = 1,000$, $W = 100$ to $W = 10,000$). The measured metrics illustrate the theoretical scaling bounds of each DP execution paradigm.

DP Paradigm StrategyTime Complexity (Big-O)Space Complexity (Big-O)Subproblem Evaluated (N=20, W=1000)Memory FootprintDecision Path Extraction
Naive Recursion$O(2^N)$$O(N)$ Stack1,048,576 CallsStack Frame OverheadReconstructed via Call Branching
Top-Down Memoization$O(N \cdot W)$$O(N \cdot W)$ Table~18,400 Calls160 KB Table + StackReconstructed via Cache Traversals
Bottom-Up 2D Tabulation$O(N \cdot W)$$O(N \cdot W)$ Matrix20,000 Grid Writes160 KB Flat MatrixDirect Backtracking through Matrix
Space-Optimized 1D Buffer$O(N \cdot W)$$O(W)$ Buffer20,000 Buffer Writes8 KB Rolling ArrayRequires Auxiliary Choice Bitset

Extensions and Stretch Goals

To extend the Dynamic Programming Workbook toward advanced dynamic programming patterns, consider the following roadmap targets:

Extension Roadmap & Engineering Targets:

  1. Tier 1 (Bitmask & Subset DP): Implement Travelling Salesperson Problem (TSP) and Matching Solvers using bitwise integer state representations.
  2. Tier 2 (Tree DP & Re-Rooting): Develop Tree Knapsack and Subtree Diameter DP engines with $O(N)$ re-rooting transformations.
  3. Tier 3 (Convex Hull Trick & Divide-and-Conquer Optimization): Implement state transition optimizations that reduce $O(N^2)$ interval DP transitions down to $O(N \log N)$.