Optimization Tool

Memoization

Memoization is top-down dynamic programming. You keep the recursive structure, but before solving a state you first ask whether it is already computed. If yes, return the cached answer immediately.

StyleTop-down DP

SpeedupCache hits

Lookup First

Every recursive call starts with a cache check. That single guard eliminates whole subtrees of repeated work.

Store on Return

Once a state is solved, save it. The next time recursion asks for the same state, you answer in O(1).

Call Stack

fib(6)

Memo Table

memo[6]?empty

memo[5]?empty

memo[4]?empty

memo[3]?empty

memo[2]?empty

memo[1]1stored

memo[0]0stored

Loading Lab...