pydp-engine 0.1.0

An intelligent, declarative Dynamic Programming engine for Python.

PyDP — an intelligent, declarative Dynamic Programming engine

PyDP lets you write Dynamic Programming solutions by declaring only the recurrence relation. The engine handles memoization, dependency analysis, execution order, memory-optimization analysis, statistics, and visualization automatically.

Describe the recurrence. Let the engine handle everything else.

from pydp import dp

@dp
def fib(solve, n):
    if n < 2:
        return n
    return solve(n - 1) + solve(n - 2)

fib(30)                 # 832040 — memoized automatically
print(fib.stats.summary())

Install

pip install -e .          # from this repo
# optional graph/plot rendering:
pip install -e ".[viz]"

Requires Python 3.9+. Zero required dependencies.

The core idea

A recurrence is a function whose first parameter is a solve handle used to request sub-states. You never write a cache, allocate a table, choose an iteration order, or add base-case bookkeeping — you express the math, and PyDP builds the machinery.

@dp
def grid_paths(solve, r, c):
    if r == 0 or c == 0:
        return 1
    return solve(r - 1, c) + solve(r, c - 1)

grid_paths(10, 10)      # 184756

Multi-argument states, string arguments, and (frozen) list arguments all work — state keys are normalized to hashable form automatically.

What you get for free after any run

Every DPProblem exposes artifacts from its most recent run:

Attribute	What it holds
.stats	PerformanceStats — states, cache hits/misses, depth, time
.graph	DependencyGraph — every state -> dependency edge
.table	the realized memo table {state: value}
.tree	the full recursion tree (parent → children)
.storage()	recommended storage backing (array / sparse / dict)

fib(20)
fib.stats.states_explored      # 21
fib.stats.hit_rate             # fraction of lookups served from cache
fib.graph.dependencies_of(6)   # {5, 4}
fib.graph.topological_order()  # dependencies-first evaluation order

Execution strategies

The same recurrence runs top-down (default), bottom-up (iterative), or parallel with no code change.

Strategy	How it evaluates
"top-down"	demand-driven recursion + memoization (default)
"bottom-up"	discovers the DAG, topologically orders it, iterates (depth 1)
"parallel"	evaluates topological layers concurrently in a thread pool
"auto"	currently resolves to top-down

fib(100, strategy="bottom-up")     # 354224848179261915075
fib.stats.max_recursion_depth      # 1

fib(100, strategy="parallel", workers=8)   # same answer, layered concurrency

@dp(strategy="bottom-up")
def knap(solve, i, cap): ...

Deep recurrences that would overflow the C stack run inside an enlarged-stack worker thread, so strategy="top-down" also handles chains thousands deep. Genuinely cyclic recurrences raise CyclicDependencyError instead of hanging.

Parallel execution

strategy="parallel" groups states into dependency layers via graph.topological_layers() — every state in a layer depends only on earlier layers, so a whole layer is evaluated concurrently. Workers get a read-only view of already-computed values, so results are deterministic regardless of thread scheduling.

fib.graph.topological_layers()   # [[0, 1], [2], [3], ...]

Note: because the recurrence body is Python, the GIL bounds CPU-bound speedup; the win is real for GIL-releasing work (I/O, NumPy), and the layering is exactly what a process-based backend would consume.

Static AST analysis

analyze() reads the recurrence's source (before it runs) and infers its structure — solve handle, state parameters, base cases, and recursive calls:

from pydp import analyze

fib = ...  # a @dp problem
print(analyze(fib).summary())
# Solve handle    : solve
# State parameters: n     (1-D)
# Base cases      : 1   -> if n < 2: return n  @line 4
# Recursive calls : 2   -> solve(n - 1), solve(n - 2)

It degrades gracefully (source_available == False) when source isn't retrievable, e.g. lambdas or REPL-defined functions.

Analysis & optimization

from pydp import analyze_memory, estimate_complexity, suggestions

fib(50)
analyze_memory(fib)       # O(n)=51 -> O(2) via rolling array
estimate_complexity(fib)  # time~O(n*k), space~O(2)
suggestions(fib)          # human-readable optimization hints

analyze_memory inspects the realized dependency graph: if every state only reaches back k steps, it reports that memory can be reduced to O(k) with a rolling array (and the analogous axis reduction for N-D grids).

Visualization

from pydp import recursion_tree, dependency_text, heatmap_text, to_graphviz

fib(7)
print(recursion_tree(fib))     # ASCII recursion tree ("cached" nodes marked)
print(dependency_text(fib))    # text dependency listing
print(heatmap_text(fib))       # visited-state heatmap (1-D and 2-D)

to_graphviz(fib, "fib_graph")  # PNG via the optional 'viz' extra

Educational mode

from pydp import explain
fib(15)
print(explain(fib))

Narrates the state space, dependency structure, a valid evaluation order, why memoization helped, the complexity estimate, and optimization suggestions.

Template library

Ready-made problems, each returning a full DPProblem (so you still get stats, graphs, and analysis):

from pydp import templates as T

T.fibonacci()(20)
T.coin_change([1, 2, 5])(11)                       # 3
T.rod_cutting([1,5,8,9,10,17,17,20])(8)            # 22
T.solve_knapsack([1,3,4,5], [1,4,5,7], 7)[0]       # 9
T.solve_lcs("AGGTAB", "GXTXAYB")[0]                # 4
T.solve_edit_distance("sunday", "saturday")[0]     # 3
T.solve_lis([10,9,2,5,3,7,101,18])[0]              # 4
T.solve_matrix_chain([40,20,30,10,30])[0]          # 26000

DP domains

Beyond the classic 1-D/2-D problems, the library ships one representative of each major DP domain, so you can see how the engine handles each shape:

# Tree DP — max-weight independent set on a rooted tree
T.solve_tree_independent_set({0:[1,2,3], 1:[4], 2:[], 3:[], 4:[]},
                             {0:10, 1:5, 2:3, 3:4, 4:8})[0]      # 18

# Interval DP — minimum palindrome-partition cuts
T.solve_palindrome_partition("aab")[0]                          # 1

# Bitmask DP — Travelling Salesman shortest tour
T.solve_tsp([[0,10,15,20],[10,0,35,25],[15,35,0,30],[20,25,30,0]])[0]  # 80

# Digit DP — count integers in [0, N] avoiding a digit
T.solve_count_without_digit(20, forbidden_digit=3)[0]           # 19

Run the tour

python examples/demo.py

Tests

pip install pytest
python -m pytest

61 tests cover the engine, all three execution strategies, cycle detection, the AST and runtime analysis modules, and every template (including the tree / interval / bitmask / digit-DP domains, the latter validated against brute force).

Architecture

Layer	Module
API / decorator	engine.dp
Core engine	engine.DPProblem
State normalization	state
Dependency analysis	graph
Static AST analysis	analyze
Storage analysis	storage
Optimizer	optimize
Visualization	visualize
Educational mode	explain
Template library	templates

License

MIT