Dynamic Programming
Memoization, recursion & DP — breaking problems into subproblems
Dynamic programming (DP) solves a hard problem by breaking it into overlapping subproblems and reusing their answers instead of recomputing them.
When does DP apply?
Two properties make a problem a DP candidate: optimal substructure (the best overall answer is built from best sub-answers) and overlapping subproblems (the same sub-answer is needed many times). The Fibonacci sequence is the textbook example — naive recursion recomputes the same values exponentially, while caching them makes it linear.
Top-down vs bottom-up
Memoization (top-down) keeps the natural recursion but caches each result the first time it is computed. Tabulation (bottom-up) fills a table from the smallest subproblems upward, often saving stack space. Both turn exponential work into polynomial work.
Recursion & backtracking
Classic teaching examples — the knapsack problem, the Tower of Hanoi and the N-Queens puzzle — show how recursion, memoization and backtracking relate. Step through them below to watch the recursion tree collapse once results are cached.
Try it interactively
0/1 Knapsack Visualizer
Animated 0/1 knapsack dynamic programming — fills the DP table cell by cell, highlighting dependencies, with step controls. Runs in your browser.
Open toolFibonacci Sequence Visualizer
Animated Fibonacci sequence — each term is the sum of the previous two, built iteratively with step controls. Runs in your browser.
Open toolTower of Hanoi Visualizer
Animated recursive Tower of Hanoi solver — moves disks in the minimum 2ⁿ−1 steps with step controls. Runs in your browser.
Open toolN-Queens Visualizer
Animated N-Queens backtracking on a chessboard — try, place, conflict, and backtrack with step controls. Runs in your browser.
Open toolFrequently asked questions
What is the difference between recursion and dynamic programming?
Recursion solves a problem by calling itself on smaller inputs; it can recompute the same subproblem many times. Dynamic programming adds memoization (top-down) or tabulation (bottom-up) so each subproblem is solved once and reused, often turning exponential time into polynomial time.
What is the difference between memoization and tabulation?
Memoization is top-down: you keep the recursive calls but cache each result the first time. Tabulation is bottom-up: you iteratively fill a table from the base cases upward. Both reuse subproblem answers; tabulation avoids recursion overhead, memoization only computes the subproblems you actually need.