Memoization (Top-Down DP)
Core Idea
Memoization caches results of overlapping subproblems. Pure recursion on Fibonacci is O(2^n); with memoization it becomes O(n) time, O(n) space.
DP Applicability Checklist
- Recursive substructure (recurrence relation exists)
- Overlapping subproblems (same subproblem solved multiple times)
- Base cases defined
Manual Memoization
def fib_memoized(n, memo=None):
if memo is None:
memo = {}
if n <= 1:
return n
[Description truncada. Veja o README completo no GitHub.]