0

Memoisation vs Brute Force

Easy

Watch the naive Fibonacci recursion explode, then watch a cache collapse it. This is the moment dynamic programming makes sense.

recursion treememoisationoverlapping subproblems
TimeO(2^n) naive, O(n) memoised
SpaceO(n)
InputA number from 4 to 9
fib(6)
modebrute force
in progressbase casereturnedcache hit

Call fib(6).

calls1
1 / 70
fib(n):
if n <= 1: return n
if memo has n: return memo[n] // the only new line
memo[n] = fib(n-1) + fib(n-2)
return memo[n]
Why it matters

Overlapping subproblems is the whole reason DP exists. The recursion tree shows them directly.

Practise this
Climbing StairsEMin Cost Climbing StairsEHouse RobberM
Keyboard
space play← → stepr restartctrl K search

More in Dynamic Programming

Kadane (Maximum Subarray)
O(n)
0/1 Knapsack
O(n * W)
Longest Common Subsequence
O(n * m)
Coin Change
O(coins * amount)
Longest Increasing Subsequence
O(n log n)
Minimum Path Sum
O(rows * cols)
Edit Distance
O(n * m)
Next visualiser
0/1 Knapsack