Math for coding interviews/Memoization - trading space for time
Memoization: Turn O(2^n) Into O(n)
The key insight: if you have already computed a result, store it. If you see the same subproblem again, look up the answer instead of recomputing. The number of unique subproblems is usually polynomial (like n², much smaller than the exponential number of total recursive calls).
See it for yourself
Two trees side by side. Left: naive recursion, the same nodes appear many times (shaded in red = duplicated work). Right: memoized version, duplicated nodes are replaced by a single cached result (green = lookup).
Memoization - trading space for time
The key insight: if you have already computed a result, store it. If you see the same subproblem again, look up the answer instead of recomputing. The number of unique subproblems is usually polynomial (like n², much smaller than the exponential number of total recursive calls).
Think of it this way: Doing your taxes every year. The first year is hard. But if you kept last year's return, you can copy and adjust instead of starting from scratch. Memoization is the filing cabinet.
For algorithms: Fibonacci without memo is O(2ⁿ). With memo it becomes O(n) because there are only n unique subproblems. DP transforms exponential problems into polynomial ones.
Real-world analogy
Doing your taxes every year. The first year is hard. But if you kept last year's return, you can copy and adjust instead of starting from scratch. Memoization is the filing cabinet.
Why it matters in interviews
Fibonacci without memo is O(2ⁿ). With memo it becomes O(n) because there are only n unique subproblems. DP transforms exponential problems into polynomial ones.