Explain DP, memoization, and tabulation.
01
01
Understand the problem
dynamic-programming
02
02
Attempt it yourself
Sketch your approach before reading the solution — that's what interviews test.
Stuck? AI Nudge Available
Get a conceptual hint to guide your logic without spoiling the final implementation.
03
03
Study the solution
The solution is waiting
Give it an honest attempt first — then compare your thinking with the full walkthrough.
04
04
Read the code
Fibonacci — naive vs memo vs tabulation
Run Playground# O(2^n) - recomputes overlapping subproblems
def fib_naive(n):
return n if n < 2 else fib_naive(n - 1) + fib_naive(n - 2)
# O(n) top-down memoization
def fib_memo(n, cache={}):
if n < 2: return n
if n not in cache:
cache[n] = fib_memo(n - 1, cache) + fib_memo(n - 2, cache)
return cache[n]
# O(n) time, O(1) space bottom-up
def fib(n):
a, b = 0, 1
for _ in range(n):
a, b = b, a + b
return a
# --- demo ---
print(fib_naive(10), fib_memo(10), fib(10)) # 55 55 5505
05
Join the discussion
Discussion (0)
Sign in to join the discussion.
No responses yet. Be the first to share what you think.