Dynamic Programming Grid Visualizer

Watch the bottom-up DP table assemble step-by-step. Hover over any cell to see its recurrence formula, subproblem inputs, and exact dependencies.

Configure Algorithm

Algorithm Mode

String A (Rows)

Letters only, max 8 chars.

String B (Cols)

Letters only, max 8 chars.

Step 1 of 1

100% Complete

Playback Interval: 1000ms

Execution Logs

DP Tabulation Matrix

ActiveMatch (+1)Mismatch (Max)

A \ B	Idx	Ø	L1	O2	N3	G4	E5	S6	T7
Ø (Empty)	0
Sidx: 1	1
Tidx: 2	2
Oidx: 3	3
Nidx: 4	4
Eidx: 5	5

💡 Hover over any filled cell to inspect its dependency connections and see the formula in the pane below!

Recurrence Formula Overlay

Core State Equation

Current Step Calculation

Processing cell [-][-]

What is Dynamic Programming (DP)?

Dynamic Programming is a powerful algorithmic technique used to solve complex problems by breaking them down into simpler subproblems. It is highly effective for optimization problems where you want to find the maximum or minimum value under specific constraints.

DP relies on two core properties:

Overlapping Subproblems: The problem can be broken down into smaller subproblems which are reused multiple times (e.g., computing $F(n-1)$ and $F(n-2)$ to find a Fibonacci number).
Optimal Substructure: The optimal solution to the global problem can be constructed efficiently from the optimal solutions of its subproblems.

The Two Approaches to DP

1. Top-Down (Memoization)

Starts with the main problem and recursively breaks it down. Solutions to subproblems are stored in a table (cache) so they are never computed twice.

2. Bottom-Up (Tabulation)

Starts by solving the smallest possible subproblems first (base cases) and iteratively fills a table (grid) to build up to the final solution. This visualizer focuses on Tabulation.

How to Use This Visualizer

Select a Problem: Choose a classic DP paradigm (like the Knapsack problem, Longest Common Subsequence, or Grid Paths).
Trace the Dependencies: Use the controls to step through execution. Cells light up to show which prior states ( $DP[i-1][j]$ , etc.) are active inputs for the current cell.
Inspect the Math: Hover over any filled cell to view the exact state transition equation applied at that specific moment.