fib(6), for the first time.
- Calls
- 1
- Recomputed
- 0
- Not reached
- On the stack
- Returned
- From the memo
- Never called
- Already solved once
01
function fib(n) {Watch a dynamic-programming table fill one cell at a time, with arrows showing which cells each one was made of — then watch the traceback walk backwards and rebuild the actual answer: the path, the coins, the items, the subsequence, the edit script, the brackets. Thirteen runs from Fibonacci's recursion tree to matrix-chain parenthesisation, and the table, the arrows and the highlighted line of code are all read from the same trace, so they never disagree.
A frontend app built by Ananda Rizki. More of them at Labs.
Dpviz
fib(n) = fib(n − 1) + fib(n − 2)
fib(6), for the first time.
function fib(n) {Simulator
Dynamic Programming Visualiser
Thirteen runs over eight problems, ordered as a curriculum rather than by difficulty: Fibonacci first, as four runs on one problem — naive recursion tree, memoised, bottom-up table, two variables — because the argument for the whole technique is watching the same tree get pruned. Then grid paths, coin change, knapsack, longest common subsequence, edit distance, longest increasing subsequence and matrix chain. Three things a printed table cannot do carry the app: arrows drawn from the cells each new cell was read from, a traceback phase that walks backwards and reconstructs the actual answer rather than just its number, and a deliberate wrong run — the knapsack rolling array iterated upwards — where per-cell item stamps make the double-count visible instead of merely described. Every traceback was checked against an independently computed answer: the edit script is replayed and has to turn one word into the other, and the matrix-chain bracketing is re-priced by multiplying it out.
Built by Ananda Rizki, a frontend developer — one of the small web apps he writes for fun at Labs.
More like this