Memoization Playground
PlaygroundsEasyTrace recursive calls and monitor memoization cache updates in top-down DP.
Alt+Shift+M
Configuration Panel
Memoization Calls and Cache State
Memoization Cache (memo[i]):
Memo table is empty.
Time Complexity
O(N) with memo / O(2^N) without
Space Complexity
O(N) cache & stack depth
Conceptual Overview
Memoization (Top-Down Dynamic Programming) optimizes naive exponential recursive algorithms by saving subproblems solutions in a cache table (like an array or hash map) and returning them directly upon repeated calls.
Recurrence Relation
fib(n) = fib(n-1) + fib(n-2) with base cases fib(0)=0, fib(1)=1
State Transitions
Caches states at heights matching subproblem values, reducing recursive branches depth from exponential O(2^N) to linear O(N) calls.
Source: CP-Algorithms dynamic programming reference