Dynamic programming, visualized
Dynamic programming clicks when you can see which earlier answers each cell reuses. These visualizations fill the table one cell at a time and highlight the cells it reads.
Start with Fibonacci to see memoisation, then knapsack and LCS for the two classic table shapes.
Start with Fibonacci Sequence (DP) 7 topics
The idea
- Fibonacci Sequence (DP)A classic example of Dynamic Programming. We calculate the Nth number by summing the two preceding ones, storing results in a table (Bottom-Up) to avoid redundant calculations.Beginner10m
- Kadane's AlgorithmFind the maximum sum contiguous subarray in O(n) time. The quintessential dynamic programming problem that every FAANG interview expects you to know.Intermediate15m
Classic tables
- 0/1 Knapsack ProblemA combinatorial optimization problem: Given a set of items, each with a weight and a value, determine which items to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible.Advanced25m
- Longest Common Subsequence (LCS)Finds the longest subsequence present in both sequences (not necessarily contiguous).Advanced25m
Advanced
- DP on TreesTree Dynamic Programming applies DP bottom-up through a rooted tree, processing children before parents in a post-order DFS so each subtree is solved exactly once. Because trees are acyclic, there are no overlapping subproblems across branches — each child's result is computed once and aggregated upward to its parent. Classic problems include finding the tree diameter, the maximum path sum (where a path can branch through a node), and the maximum weight independent set (where chosen nodes cannot be adjacent). This visualization animates the Maximum Path Sum algorithm on a five-node binary tree, showing how each node separately tracks the best downward path to return to its parent and the best full path through itself that updates the global answer.Advanced35m
- Bitmask DP (State Compression)Use bits to represent subset states, enabling DP over all subsets efficiently. Essential for Travelling Salesman, subset selection, and assignment problems.Advanced40m
- Backtracking (N-Queens)Solve complex problems by building candidates step-by-step and abandoning them ("backtracking") as soon as they fail constraints.AdvancedCode30m