Memoization
memoization
Algorithms
Dynamic Programming (Intro)
Naive recursive Fibonacci computes `fib(40)` in seconds, `fib(50)` in minutes, and gives up on `fib(60)`, all because it recomputes the same subproblems exponentially many times. Cache the result of each `fib(k)` the first time you compute it and the same recursion runs in linear time. That single change, remembering answers, is the entire content of dynamic programming. **Dynamic Programming (Intro)** turns that observation into a complete problem-solving framework. You will identify overlapping subproblems and optimal substructure (the two properties a problem must have for DP to apply), and master both approaches: top-down memoization (recursion plus a cache) and bottom-up tabulation (iteratively filling a table). Classic 1D problems include Fibonacci, climbing stairs, coin change, house robber, and a first look at Kadane's algorithm. The lesson teaches you to define state precisely ("what does `dp[i]` represent?"), write the transition ("how does `dp[i]` follow from earlier states?"), set base cases, and apply rolling-variable space optimization that drops `O(n)` to `O(1)`. In **Recursion Fundamentals**, you treated each recursive call as a stack frame. Memoization just attaches a cache so identical inputs return immediately. Next, **Bit Manipulation (Intro)** turns to a different toolkit, where bitwise operators give elegant `O(1)` solutions.
Not Started
0%
Practice Problems
Climbing Stairs
Given n steps, find the number of distinct ways to climb to the top when you can take 1 or 2 steps at a time.
Longest Increasing Path in a Matrix
Given an m x n integer matrix, find the length of the longest strictly increasing path where you can move in four directions.
House Robber
Given an array representing the amount of money in each house along a street, determine the maximum amount you can rob without robbing two adjacent houses.
Code Snippets
Memoize Higher-Order Function
Memoization caches function results keyed by arguments so repeat calls return in O(1). This snippet covers the canonical single-arg memoize, a multi-arg version that handles object identity via a `Map` chain, and an LRU-bounded variant that prevents unbounded cache growth. Use it for pure functions whose work dwarfs the lookup cost (parsing, layout calc, recursive DP).
Fibonacci: Iterative, Recursive, Memoized, Generator
Fibonacci is the canonical exercise for comparing iteration, recursion, memoization, and lazy evaluation. The iterative for-loop is the production answer, naive recursion is the cautionary tale (exponential cost), memoization fixes the recursion to linear time, and a generator yields an infinite stream you can `take(n)` from. Above index 78, switch to BigInt to avoid floating-point precision loss.
Question Banks
Dynamic Programming Warm-Up
Memoization, tabulation, and writing transitions for classic 1D DP. Code stems are Python.
React Performance Optimization Quiz
Five drills on memoization, stable references, PureComponent, and the trade-offs between fixing a real render-cost problem and prematurely wrapping everything in memo.
Community
Why My Context Provider Was Re-rendering Everything
We added a flame-graph and saw every consumer of `<UserContext>` re-rendering on every keystroke in a sibling. The fix took two days to isolate and three lines to ship.
Space Complexity, the Other Half of the Story
Auxiliary vs input space, the recursion-stack trap, the time-vs-space trade, and the two questions I added to my code-review template after one OOM in production.
Word Break II
Return every sentence that can be formed by space-segmenting a string into dictionary words, using memoized DFS keyed by start index.
Dynamic Programming Patterns
A 5-step framework that turns DP from magic into a checklist, the six recurring patterns, and the memoization-vs-tabulation decision that hides every space optimization.
When `memo` Actually Stops a Re-render (and When It Does Not)
I once added React.memo everywhere and renders barely changed. Memo only works under specific conditions, and outside those it is dead weight. Three accordions on the trap and the fix.
DP Questions I Saw Coming and Still Missed
Four DP problems I recognized in the interview and still got wrong. Coin change with the wrong order of loops, LIS in O(n^2), edit distance with a missing base case, and a 2D grid DP with overcounted moves.
Memoize With TTL and Bounded Cache Size
The official memoize is unbounded and has no TTL, which works in tests and leaks memory in production. This is the version I ship: bounded LRU + per-entry expiry, in 40 lines.